Check If Two String Arrays are Equivalent

Difficulty: Easy | Acceptance: 86.10% | Paid: No Topics: Array, String

Given two string arrays word1 and word2, return true if the two arrays represent the same string. A string is represented by an array if the array elements concatenated in order forms the string.

• Examples
• Constraints
• Concatenation
• Two Pointers

Examples

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false
Explanation:
word1 represents string "a" + "cb" -> "acb"
word2 represents string "ab" + "c" -> "abc"
The strings are not the same, so return false.

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true
Explanation:
word1 represents string "abc" + "d" + "defg" -> "abcddefg"
word2 represents string "abcddefg"
The strings are the same, so return true.

Constraints

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Concatenation

Intuition The most straightforward way to check if two arrays of strings represent the same string is to concatenate all strings in each array into a single string and then compare the results.

Steps

• Concatenate all strings in word1 into a single string s1.
• Concatenate all strings in word2 into a single string s2.
• Return true if s1 equals s2, otherwise return false.

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

Complexity

• Time: O(N + M), where N and M are the total number of characters in word1 and word2 respectively.
• Space: O(N + M) to store the concatenated strings.
• Notes: This approach is simple and readable but uses extra memory proportional to the input size.

Two Pointers

Intuition To optimize space, we can compare the arrays character by character without constructing the full strings. We use pointers to track the current word and the current character within that word for both arrays.

Steps

• Initialize pointers i1 and i2 for the word indices in word1 and word2, and j1 and j2 for the character indices within the current words.
• While both pointers are within bounds:
  • Compare word1[i1][j1] with word2[i2][j2]. If they differ, return false.
  • Increment j1 and j2.
  • If j1 reaches the end of word1[i1], move to the next word (i1++) and reset j1 to 0.
  • If j2 reaches the end of word2[i2], move to the next word (i2++) and reset j2 to 0.
• After the loop, return true only if both arrays have been fully traversed (i.e., i1 equals word1.length and i2 equals word2.length).

class Solution:
    def arrayStringsAreEqual(self, word1: list[str], word2: list[str]) -> bool:
        i1 = i2 = 0
        j1 = j2 = 0
        while i1 < len(word1) and i2 < len(word2):
            if word1[i1][j1] != word2[i2][j2]:
                return False
            j1 += 1
            j2 += 1
            if j1 == len(word1[i1]):
                i1 += 1
                j1 = 0
            if j2 == len(word2[i2]):
                i2 += 1
                j2 = 0
        return i1 == len(word1) and i2 == len(word2)

Complexity

• Time: O(N + M), where N and M are the total number of characters in word1 and word2 respectively.
• Space: O(1), as we only use a constant amount of extra space for pointers.
• Notes: This is the optimal solution for space efficiency, especially useful when dealing with very large strings.