Check If Two String Arrays are Equivalent

Easy

#1525Time: O(N + M), where N is the total number of characters in `word1` and M is the total number of characters in `word2`. We need to iterate through all characters to build the strings.Space: O(N + M). We need extra space to store the two concatenated strings, where N is the total length of strings in `word1` and M is the total length of strings in `word2`.

Data structures

Array String

Prompt

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

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

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves creating the two complete strings by concatenating the elements of each array and then comparing the resulting strings.

Algorithm

Create a StringBuilder sb1.
Iterate through word1 and append each string to sb1.
Create a StringBuilder sb2.
Iterate through word2 and append each string to sb2.
Return the result of sb1.toString().equals(sb2.toString()).

Walkthrough

The idea is to simulate the process described in the problem directly. We build two strings, one for each input array.

Initialize two StringBuilder objects, sb1 and sb2.
Iterate through the word1 array. For each string s in word1, append it to sb1.
Iterate through the word2 array. For each string s in word2, append it to sb2.
After building both strings, convert the StringBuilder objects to String objects.
Compare the two resulting strings using the .equals() method. If they are identical, return true; otherwise, return false.

1class Solution {2    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {3        StringBuilder sb1 = new StringBuilder();4        for (String s : word1) {5            sb1.append(s);6        }7 8        StringBuilder sb2 = new StringBuilder();9        for (String s : word2) {10            sb2.append(s);11        }12 13        return sb1.toString().equals(sb2.toString());14    }15}

A more concise way to write this in Java using String.join:

1class Solution {2    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {3        return String.join("", word1).equals(String.join("", word2));4    }5}

Complexity

Time

O(N + M), where N is the total number of characters in `word1` and M is the total number of characters in `word2`. We need to iterate through all characters to build the strings.

Space

O(N + M). We need extra space to store the two concatenated strings, where N is the total length of strings in `word1` and M is the total length of strings in `word2`.

Trade-offs

Pros

Very simple and intuitive to implement.
Code is clean and easy to read, especially with helpers like String.join.

Cons

Inefficient in terms of space, as it requires creating copies of all the characters in memory.
Can be slow if the total length of strings is very large due to memory allocation.

This approach avoids creating the intermediate concatenated strings by comparing the characters one by one using pointers. This is significantly more memory-efficient.

Algorithm

Initialize pointers for word1 (w1, c1) and word2 (w2, c2) to 0.
Use a while loop that continues as long as w1 < word1.length and w2 < word2.length.
Inside the loop, if word1[w1].charAt(c1) is not equal to word2[w2].charAt(c2), return false.
Increment c1 and c2.
If c1 is at the end of word1[w1], increment w1 and reset c1 to 0.
If c2 is at the end of word2[w2], increment w2 and reset c2 to 0.
After the loop, return true only if both w1 has reached the end of word1 and w2 has reached the end of word2.

Walkthrough

Instead of building the full strings, we can simulate the comparison character by character. We use pointers to track our current position within the arrays of strings and within the strings themselves.

Initialize four pointers: w1 (index for word1), c1 (character index for word1[w1]), w2 (index for word2), and c2 (character index for word2[w2]). All start at 0.
Loop as long as both w1 and w2 are within the bounds of their respective arrays.
Inside the loop, compare the characters: word1[w1].charAt(c1) and word2[w2].charAt(c2). If they don't match, the strings are not equivalent, so return false.
Increment both character pointers, c1 and c2.
If c1 reaches the end of the current string word1[w1], it means we've finished this word. We move to the next word by incrementing w1 and resetting c1 to 0.
Similarly, if c2 reaches the end of word2[w2], increment w2 and reset c2 to 0.
After the loop terminates, it means we've exhausted at least one of the arrays. For the strings to be truly equal, both arrays must be fully traversed. We check if w1 has reached the end of word1 AND w2 has reached the end of word2. If both conditions are true, it means they are equivalent. Otherwise, one is a prefix of the other, and they are not equal.

1class Solution {2    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {3        int w1 = 0, c1 = 0; // Pointers for word14        int w2 = 0, c2 = 0; // Pointers for word25 6        while (w1 < word1.length && w2 < word2.length) {7            // Get the current characters to compare8            char char1 = word1[w1].charAt(c1);9            char char2 = word2[w2].charAt(c2);10 11            if (char1 != char2) {12                return false;13            }14 15            // Move to the next character16            c1++;17            c2++;18 19            // If we reached the end of a string in word1, move to the next string20            if (c1 == word1[w1].length()) {21                w1++;22                c1 = 0;23            }24 25            // If we reached the end of a string in word2, move to the next string26            if (c2 == word2[w2].length()) {27                w2++;28                c2 = 0;29            }30        }31 32        // After the loop, both arrays must be fully traversed for the strings to be equal.33        return w1 == word1.length && w2 == word2.length;34    }35}

Complexity

Time

O(min(N, M)), where N and M are the total character counts. In the worst case (equal strings), it's O(N) as we traverse every character once. The comparison stops as soon as a mismatch is found.

Space

O(1). We only use a few integer variables for pointers, regardless of the input size.

Trade-offs

Pros

Extremely memory efficient (O(1) space).
Can be faster in practice if the strings differ early on, as it allows for early exit.

Cons

The implementation logic is more complex and requires careful handling of multiple pointers and boundary conditions.

Solutions

Solution

1class Solution { public boolean arrayStringsAreEqual ( String [] word1 , String [] word2 ) { return String . join ( "" , word1 ). equals ( String . join ( "" , word2 )); } }

1class Solution { public: bool arrayStringsAreEqual ( vector < string >& word1 , vector < string >& word2 ) { return reduce ( word1 . cbegin (), word1 . cend ()) == reduce ( word2 . cbegin (), word2 . cend ()); } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem