1662. Check If Two String Arrays are Equivalent - Explanation

Problem Link

1. Concatenate Strings

Intuition

The simplest approach is to concatenate all strings in each array into a single string, then compare the two resulting strings. If they match character by character, the arrays represent the same string.

Algorithm

1. Join all strings in word1 into a single string.
2. Join all strings in word2 into a single string.
3. Compare the two concatenated strings.
4. Return true if they are equal, false otherwise.

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        return "".join(word1) == "".join(word2)

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n + m)$

Where $n$ and $m$ are the total number of characters in both the arrays $word1$ and $word2$, respectively.

---

2. Concatenate Strings Of One Array

Intuition

We can reduce space usage by only concatenating one of the arrays. We then iterate through the second array character by character, comparing each character against the concatenated string. This way, we only build one full string instead of two.

Algorithm

1. Concatenate all strings in word1 into a single string s1.
2. Initialize an index pointer i to 0.
3. Iterate through each string in word2, then through each character in that string.
4. For each character, check if the index has exceeded s1's length or if the characters do not match.
5. If either condition is true, return false immediately.
6. Increment the index after each successful comparison.
7. After processing all of word2, return true only if i equals the length of s1 (ensuring both have the same length).

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        s1 = "".join(word1)
        i = 0
        for w in word2:
            for c in w:
                if i == len(s1) or s1[i] != c:
                    return False
                i += 1
        return i == len(s1)

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(n)$

Where $n$ and $m$ are the total number of characters in both the arrays $word1$ and $word2$, respectively.

---

3. Two Pointers

Intuition

We can avoid creating any concatenated strings by using four pointers: two to track which string we are currently in (one for each array), and two to track the character position within those strings. We compare characters one at a time, advancing through both arrays simultaneously.

Algorithm

1. Initialize four pointers: w1 and w2 for the current word index in each array, i and j for the character position within the current words.
2. While both arrays have more content to process:
   • Compare the current characters from both arrays.
   • If they differ, return false.
   • Advance both character pointers.
   • If a character pointer reaches the end of its current word, move to the next word and reset the character pointer to 0.
3. After the loop, check that both arrays have been fully processed (both word pointers have reached the end).
4. Return true if both arrays are exhausted, false otherwise.

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        w1 = w2 = 0  # Index of word
        i = j = 0    # Index of character

        while w1 < len(word1) and w2 < len(word2):
            if word1[w1][i] != word2[w2][j]:
                return False

            i, j = i + 1, j + 1

            if i == len(word1[w1]):
                w1 += 1
                i = 0
            if j == len(word2[w2]):
                w2 += 1
                j = 0

        return w1 == len(word1) and w2 == len(word2)

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(1)$ extra space.

Where $n$ and $m$ are the total number of characters in both the arrays $word1$ and $word2$, respectively.

---

Common Pitfalls

Forgetting the Final Length Check

When iterating through one array while comparing to the concatenated string of the other, returning true after matching all characters without verifying both strings have the same length. If word2 is shorter than word1, all characters may match but the strings are not equivalent.

# Wrong: missing final length check
return True

# Correct: verify all characters were consumed
return i == len(s1)

Comparing Array Lengths Instead of Total Characters

Assuming arrays with the same number of elements will produce equivalent strings. The arrays ["ab", "c"] and ["a", "bc"] have different lengths but represent the same string "abc".