💬 Discord
Sign In
NeetCode #191LC-1662EasyTwo Pointers
← Back to All Problems

#191 · #1662 · Check If Two String Arrays are Equivalent(检查两个字符串数组是否相等)

📌 Problem Statement & Constraints

Given two string arrays word1 and word2, return whether the two arrays represent the same string when concatenated. Constraints: 1 <= word1.length, word2.length <= 10^3, 1 <= word1[i].length, word2[i].length <= 10^3.

💡 Core Algorithmic Approaches

  1. The simplest approach concatenates each array and compares the results, which is O(total characters) time and space.
  2. A follow-up asks for O(1) extra space: use four pointers -- an array index and a character index for each side -- and compare characters one at a time, advancing to the next word when a word is exhausted.
  3. Both versions are O(total characters) time; only the space differs.
  4. The pointer version is a good exercise in multi-pointer bookkeeping.

💻 Benchmark Python3 Implementation

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


# O(1)-space variant: four pointers, comparing character by character
class Solution2:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        i = j = 0                      # word indices
        p = q = 0                      # character indices within words
        while i < len(word1) and j < len(word2):
            if word1[i][p] != word2[j][q]:
                return False
            p += 1
            q += 1
            if p == len(word1[i]):     # word exhausted -> advance
                i += 1
                p = 0
            if q == len(word2[j]):
                j += 1
                q = 0
        # equal only if both sides are fully consumed
        return i == len(word1) and j == len(word2)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total characters): each character is compared once in both variants.
💾 Space Complexity
O(total characters) for the join; O(1) for the pointer variant.

⚠️ Interview Pitfalls & Follow-ups

  • Using == on the arrays themselves: ["ab", "c"] and ["a", "bc"] are different arrays but the same string.
  • Comparing the concatenations without accounting for word boundaries: joining handles this correctly, and the pointer variant advances the word index at the boundary.
  • Forgetting the final exhaustion check in the pointer variant: one side may finish earlier, in which case the strings differ in length.
  • Assuming word lengths are equal: they need not be, which is exactly what the pointer bookkeeping handles.