LeetCode 1662 - Check If Two String Arrays are Equivalent

LeetCode Problem 1662

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem gives us two arrays of strings, word1 and word2. Each array represents a single larger string formed by concatenating all of its elements in order. Our task is to determine whether the final strings produced by both arrays are exactly the same.

For example, if:

word1 = ["ab", "c"]
word2 = ["a", "bc"]

then:

word1 -> "ab" + "c" = "abc"
word2 -> "a" + "bc" = "abc"

Since both arrays produce the same final string, the answer is true.

The important detail is that the comparison is based on the fully concatenated result, not on the structure of the arrays themselves. The arrays may have different numbers of elements, and the boundaries between strings do not matter. Only the final sequence of characters matters.

The constraints are relatively small. The total number of characters across each array is at most 10^3, which means even straightforward approaches are fast enough. However, this problem is designed to test understanding of string handling and efficient comparison techniques.

The input guarantees that:

• Each array contains at least one string
• Each string contains only lowercase English letters
• Total combined character counts are manageable

Several edge cases are important to think about:

• Arrays with different partitioning but identical final strings
• Arrays with different total lengths
• Arrays where mismatch happens early
• Arrays containing many very small strings
• Arrays containing a single large string

A naive implementation might incorrectly compare arrays element by element instead of comparing the resulting concatenated strings.

Approaches

Brute Force Approach

The simplest solution is to concatenate all strings in word1 into one large string, concatenate all strings in word2 into another large string, and compare the results.

In Python, this can be done using "".join(word1) and "".join(word2). In Go, we can use a string builder or repeated concatenation.

This approach works because the problem definition directly states that each array represents the concatenation of its elements. Once we construct both full strings, checking equality becomes trivial.

The downside is that we allocate additional memory for the concatenated strings. Although the constraints are small enough that this is completely acceptable, it is not the most memory efficient solution.

Optimal Approach

A more efficient approach compares characters one by one without constructing the full strings.

The key insight is that we do not actually need the concatenated strings themselves. We only need to verify that both arrays generate the same sequence of characters.

We can maintain:

• An index for the current string in word1
• An index for the current character inside that string
• The same pair of indices for word2

At every step, we compare the current characters from both arrays. If they differ, we immediately return false. If they match, we advance the corresponding character pointers. When we reach the end of a string, we move to the next string in the array.

This avoids creating temporary concatenated strings and performs the comparison in a streaming fashion.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + m)	O(n + m)	Builds complete concatenated strings before comparing
Optimal	O(n + m)	O(1)	Compares characters directly without extra string allocation

Here, n and m are the total number of characters in word1 and word2.

Algorithm Walkthrough

1. Initialize four pointers:

• i for the current string index in word1
• j for the current character index inside word1[i]
• k for the current string index in word2
• l for the current character index inside word2[k]

2. Continue looping while both arrays still contain characters to process.
3. Compare the current characters:

word1[i][j] vs word2[k][l]

If they are different, immediately return false because the represented strings cannot be equal. 4. Advance both character pointers:

• Increment j
• Increment l

5. If j reaches the length of word1[i], move to the next string:

• Increment i
• Reset j to 0

6. If l reaches the length of word2[k], move to the next string:

• Increment k
• Reset l to 0

7. Continue until one or both arrays are fully processed.
8. At the end, return true only if both arrays were completely consumed at the same time.

Why it works

The algorithm maintains the invariant that all previously compared characters are equal. At every step, it compares the next character in the logical concatenated strings. Since characters are processed in order and every character must match, the algorithm correctly determines whether the represented strings are identical.

Python Solution

from typing import List

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        i = j = 0
        k = l = 0

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

            j += 1
            l += 1

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

            if l == len(word2[k]):
                k += 1
                l = 0

        return i == len(word1) and k == len(word2)

The implementation follows the pointer-based algorithm exactly.

The variables i and j track the current location inside word1, while k and l track the current location inside word2.

Inside the loop, the algorithm compares one character at a time. If a mismatch is found, it immediately returns False.

After each successful comparison, the character pointers move forward. When a pointer reaches the end of its current string, the algorithm advances to the next string and resets the character position back to zero.

Finally, the solution verifies that both arrays were fully consumed. This ensures that neither represented string contains extra unmatched characters.

Go Solution

func arrayStringsAreEqual(word1 []string, word2 []string) bool {
	i, j := 0, 0
	k, l := 0, 0

	for i < len(word1) && k < len(word2) {
		if word1[i][j] != word2[k][l] {
			return false
		}

		j++
		l++

		if j == len(word1[i]) {
			i++
			j = 0
		}

		if l == len(word2[k]) {
			k++
			l = 0
		}
	}

	return i == len(word1) && k == len(word2)
}

The Go implementation mirrors the Python solution closely.

Go strings are byte indexed, which works correctly here because the problem guarantees lowercase English letters only. If Unicode characters were involved, we would need rune handling instead.

The solution uses integer indices directly into the string slices and character positions. Since the constraints are small, there are no concerns about integer overflow.

Nil slices and empty slices are not an issue because the constraints guarantee at least one string in each array.

Worked Examples

Example 1

word1 = ["ab", "c"]
word2 = ["a", "bc"]

The represented strings are both "abc".

Step	word1 Position	Character	word2 Position	Character	Result
1	word1[0][0]	a	word2[0][0]	a	match
2	word1[0][1]	b	word2[1][0]	b	match
3	word1[1][0]	c	word2[1][1]	c	match

After processing all characters, both arrays are exhausted simultaneously, so the answer is true.

Example 2

word1 = ["a", "cb"]
word2 = ["ab", "c"]

The represented strings are "acb" and "abc".

Step	word1 Position	Character	word2 Position	Character	Result
1	word1[0][0]	a	word2[0][0]	a	match
2	word1[1][0]	c	word2[0][1]	b	mismatch

A mismatch occurs immediately at step 2, so the answer is false.

Example 3

word1 = ["abc", "d", "defg"]
word2 = ["abcddefg"]

Both arrays represent "abcddefg".

Step	Character from word1	Character from word2	Result
1	a	a	match
2	b	b	match
3	c	c	match
4	d	d	match
5	d	d	match
6	e	e	match
7	f	f	match
8	g	g	match

All characters match, so the answer is true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Every character from both arrays is visited at most once
Space	O(1)	Only a few index variables are used

The algorithm performs a single pass through both represented strings. Since each character is processed exactly once, the running time is linear in the total input size.

The solution uses constant extra memory because it only stores index pointers and does not allocate additional concatenated strings.

Test Cases

sol = Solution()

# Provided examples
assert sol.arrayStringsAreEqual(["ab", "c"], ["a", "bc"]) is True  # same final string
assert sol.arrayStringsAreEqual(["a", "cb"], ["ab", "c"]) is False  # mismatch in middle
assert sol.arrayStringsAreEqual(["abc", "d", "defg"], ["abcddefg"]) is True  # different partitioning

# Single element arrays
assert sol.arrayStringsAreEqual(["hello"], ["hello"]) is True  # identical single strings
assert sol.arrayStringsAreEqual(["hello"], ["world"]) is False  # completely different

# Different partition layouts
assert sol.arrayStringsAreEqual(["a", "b", "c"], ["abc"]) is True  # many small pieces
assert sol.arrayStringsAreEqual(["ab", "cd"], ["a", "bcd"]) is True  # uneven partitioning

# Different total lengths
assert sol.arrayStringsAreEqual(["abc"], ["ab"]) is False  # second shorter
assert sol.arrayStringsAreEqual(["ab"], ["abc"]) is False  # first shorter

# Early mismatch
assert sol.arrayStringsAreEqual(["xabc"], ["yabc"]) is False  # mismatch at beginning

# Late mismatch
assert sol.arrayStringsAreEqual(["abcd"], ["abce"]) is False  # mismatch at end

# Many tiny strings
assert sol.arrayStringsAreEqual(
    ["a", "a", "a", "a"],
    ["aaaa"]
) is True  # repeated small fragments

# Boundary style test
assert sol.arrayStringsAreEqual(
    ["a" * 1000],
    ["a" * 500, "a" * 500]
) is True  # large strings with different grouping

Test	Why
["ab","c"] vs ["a","bc"]	Validates standard matching case
["a","cb"] vs ["ab","c"]	Validates mismatch detection
["abc","d","defg"] vs ["abcddefg"]	Confirms grouping does not matter
["hello"] vs ["hello"]	Tests identical single strings
["hello"] vs ["world"]	Tests completely different strings
["a","b","c"] vs ["abc"]	Tests many small fragments
["ab","cd"] vs ["a","bcd"]	Tests uneven partition boundaries
["abc"] vs ["ab"]	Tests different total lengths
["ab"] vs ["abc"]	Tests opposite length mismatch
["xabc"] vs ["yabc"]	Tests early mismatch
["abcd"] vs ["abce"]	Tests late mismatch
Multiple "a" fragments vs "aaaa"	Tests repeated tiny strings
Large repeated string test	Tests near-constraint input sizes

Edge Cases

One important edge case is when the arrays have different partition boundaries but still represent the same final string. For example:

["ab", "c"] vs ["a", "bc"]

A buggy implementation that compares array elements directly would incorrectly return false. The pointer-based solution avoids this issue because it compares characters sequentially rather than comparing array structure.

Another important edge case is when the total lengths differ. For example:

["abc"] vs ["ab"]

Even if all compared characters initially match, one represented string ends earlier. The implementation handles this correctly by checking that both arrays are fully consumed at the same time before returning true.

A third important edge case is mismatches occurring across string boundaries. For example:

["ab", "x"] vs ["a", "bc"]

The mismatch happens only after moving from one string segment to another. Pointer transition logic is often a source of off by one errors, but this implementation carefully resets character indices whenever the end of a string is reached, ensuring comparisons continue correctly across boundaries.