Check If Two String Arrays are Equivalent

How it works

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.

Steps

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.

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.

Things to watch for

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.

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".

from typing import List

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)

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        int w1 = 0, w2 = 0; // Index of word
        int i = 0, j = 0;   // Index of character

        while (w1 < word1.size() && w2 < word2.size()) {
            if (word1[w1][i] != word2[w2][j]) {
                return false;
            }

            i++;
            j++;

            if (i == word1[w1].size()) {
                w1++;
                i = 0;
            }
            if (j == word2[w2].size()) {
                w2++;
                j = 0;
            }
        }
        return w1 == word1.size() && w2 == word2.size();
    }
};