Check If Two String Arrays are Equivalent - Solution & Explanation
Problem Statement
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 <= 1031 <= word1[i].length, word2[i].length <= 1031 <= sum(word1[i].length), sum(word2[i].length) <= 103word1[i]andword2[i]consist of lowercase letters.
Approach Overview
Problem Overview: You receive two arrays of strings, word1 and word2. When all elements in each array are concatenated, they form two full strings. The task is to check whether those resulting strings are identical without misinterpreting character order.
Approach 1: String Concatenation (O(n) time, O(n) space)
The most direct solution is to concatenate all strings in word1 into a single string and do the same for word2. After building the two final strings, perform a simple equality check. This works because string equality guarantees both length and character order match. The total runtime is O(n), where n is the total number of characters across both arrays, since every character is copied once. Space complexity is also O(n) because two new strings are created.
This approach is clean and easy to implement in any language. However, it allocates extra memory for the combined strings. For small inputs this cost is negligible, but interviewers often expect you to recognize that the comparison can be done without building the full strings.
Approach 2: Two-Pointer Character Comparison (O(n) time, O(1) space)
A more efficient approach compares characters directly using pointers. Maintain two indices: one for the current string in word1 and another for word2, along with character positions inside those strings. Iterate character by character, comparing the current characters from both arrays. When you reach the end of a string in either array, move the pointer to the next string and reset the character index.
This method processes characters sequentially without constructing intermediate strings. Every character is visited exactly once, so the runtime remains O(n). Since only a few pointer variables are used, the space complexity is O(1). This technique resembles streaming comparison and is common in string processing problems where memory efficiency matters.
The logic relies on careful pointer movement across array boundaries, making it a good exercise in handling nested iteration across array elements while maintaining character-level comparison.
Recommended for interviews: The two-pointer approach is typically preferred. It demonstrates awareness of unnecessary memory allocations and shows you can iterate across segmented strings efficiently. Starting with the concatenation solution shows clear thinking, but transitioning to the pointer-based optimization highlights strong problem-solving skills and familiarity with two-pointer techniques.
Approach 1: String Concatenation Approach
This approach involves concatenating all the elements in each string array to form two complete strings, and then comparing these strings for equality. Since we need to ensure that the concatenated results of the two arrays are the same, this approach is both intuitive and straightforward.
This C program uses the strcat function to concatenate all the parts of word1 and word2 into two separate strings. It then applies strcmp to check if these strings are identical, returning true if they are; otherwise, false. The buffer sizes are assumed to be within bounds because of the constraints given in the problem.
Complexity
The time complexity is O(n), where n is the sum of the lengths of both arrays' strings, as each character is traversed once during concatenation. The space complexity is O(n) due to the storage of the concatenated strings.
Approach 2: Two-Pointer Approach
Instead of explicitly concatenating the arrays into strings, this approach uses two pointers to iterate through the characters of the arrays simultaneously. It allows checking one character at a time across both arrays, ensuring they match without creating additional strings.
This C solution uses multiple iterators to navigate through the arrays without creating concatenated strings. Characters are compared directly during iteration until all characters in both arrays have been evaluated.
Complexity
Time complexity is O(n), where n is the total number of characters in both arrays. Space complexity is minimized to O(1) as no additional storage is required beyond basic variables.
Approach 3: String Concatenation
Concatenate the strings in the two arrays into two strings, then compare whether the two strings are equal.
The time complexity is O(m), and the space complexity is O(m). Here, m is the total length of the strings in the arrays.
Approach 4: Direct Traversal
In Solution 1, we concatenated the strings in the two arrays into two new strings, which has additional space overhead. We can also directly traverse the two arrays and compare the characters one by one.
We use two pointers i and j to point to the two string arrays, and another two pointers x and y to point to the corresponding characters in the strings. Initially, i = j = x = y = 0.
Each time we compare word1[i][x] and word2[j][y]. If they are not equal, we directly return false. Otherwise, we increment x and y by 1. If x or y exceeds the length of the corresponding string, we increment the corresponding string pointer i or j by 1, and then reset x and y to 0.
If both string arrays are traversed, we return true, otherwise, we return false.
The time complexity is O(m), and the space complexity is O(1). Here, m is the total length of the strings in the arrays.
Complexity Comparison
| Approach | Complexity |
|---|---|
| String Concatenation Approach | The time complexity is O(n), where n is the sum of the lengths of both arrays' strings, as each character is traversed once during concatenation. The space complexity is O(n) due to the storage of the concatenated strings. |
| Two-Pointer Approach | Time complexity is O(n), where n is the total number of characters in both arrays. Space complexity is minimized to O(1) as no additional storage is required beyond basic variables. |
| String Concatenation | — |
| Direct Traversal | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Concatenation | O(n) | O(n) | Best for quick implementation or when memory usage is not a concern. |
| Two-Pointer Character Comparison | O(n) | O(1) | Preferred when avoiding extra string allocation or when optimizing memory usage. |
Video Solution
Check If Two String Arrays are Equivalent | Goldman Sachs | Explanation | Live Coding • codestorywithMIK • 18,544 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check If Two String Arrays are Equivalent easy or hard?
Check If Two String Arrays are Equivalent Python/Java solution
How to solve Check If Two String Arrays are Equivalent in O(n)?
What is the best approach for Check If Two String Arrays are Equivalent?
Is Check If Two String Arrays are Equivalent asked at Google/Amazon/Meta?
What data structure is used in Check If Two String Arrays are Equivalent?
What is the time complexity of Check If Two String Arrays are Equivalent?
Ready to solve this problem?
Practice Check If Two String Arrays are Equivalent with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor