Check If Two String Arrays are Equivalent solution and explanation
Google
9 more videos on this problem
Check If Two String Arrays are Equivalent | Goldman Sachs | Explanation | Live CodingcodestorywithMIK · 14:39 · 18K views
Check If Two String Arrays are Equivalent - Leetcode 1662 - PythonNeetCodeIO · 7:05 · 8K views
Check If Two String Arrays are Equivalent | Live Coding with Explanation | Leetcode #1662Algorithms Made Easy · 6:11 · 3K views
1662. Check If Two String Arrays are Equivalent | O(1) SpaceAryan Mittal · 9:02 · 1K views
Leetcode - Check If Two String Arrays are Equivalent (Python)Timothy H Chang · 5:39 · 1K views
Check If Two String Arrays are Equivalent | Leetcode 1662 | leetcode solutionEasyLeetcode · 8:54 · 1K views
Check If Two String Arrays are Equivalent | Leet code 1662 | Theory explained + Python codeSai Anish Malla · 10:48 · 1K views
Leetcode | 1662. Check If Two String Arrays are Equivalent | Easy | Java SolutionDeveloper Docs · 3:27 · 822 views
1662. Check If Two String Arrays are Equivalent (Leetcode Easy)Programming Live with Larry · 2:06 · 529 views
Leetcode Solution - 1662 Check If Two String Arrays are EquivalentJohn Leonardo · 2:10 · 358 views
The problem
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.
def arrayStringsAreEqual(word1, word2):
return ''.join(word1) == ''.join(word2)
word1 = ["abc", "d", "defg"]
word2 = ["abcddefg"]
print(arrayStringsAreEqual(word1, word2))import java.util.*;
public class Main {
public static boolean arrayStringsAreEqual(String[] word1, String[] word2) {
StringBuilder s1 = new StringBuilder();
StringBuilder s2 = new StringBuilder();
for (String w : word1) s1.append(w);
for (String w : word2) s2.append(w);
return s1.toString().equals(s2.toString());
}
public static void main(String[] args) {
String[] word1 = {"abc", "d", "defg"};
String[] word2 = {"abcddefg"};
System.out.println(arrayStringsAreEqual(word1, word2));
}
}#include <iostream>
#include <vector>
using namespace std;
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
string s1 = "", s2 = "";
for (const string &w : word1) s1 += w;
for (const string &w : word2) s2 += w;
return s1 == s2;
}
int main() {
vector<string> word1 = {"abc", "d", "defg"};
vector<string> word2 = {"abcddefg"};
cout << (arrayStringsAreEqual(word1, word2) ? "true" : "false") << endl;
return 0;
}function arrayStringsAreEqual(word1, word2) {
return word1.join('') === word2.join('');
}
const word1 = ["abc", "d", "defg"];
const word2 = ["abcddefg"];
console.log(arrayStringsAreEqual(word1, word2));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool arrayStringsAreEqual(char ** word1, int word1Size, char ** word2, int word2Size){
char str1[1001] = "";
char str2[1001] = "";
for (int i = 0; i < word1Size; i++) {
strcat(str1, word1[i]);
}
for (int i = 0; i < word2Size; i++) {
strcat(str2, word2[i]);
}
return strcmp(str1, str2) == 0;
}
int main() {
char *word1[] = {"abc", "d", "defg"};
char *word2[] = {"abcddefg"};
printf("%s\n", arrayStringsAreEqual(word1, 3, word2, 1) ? "true" : "false");
return 0;
}using System;
public class Solution {
public static bool ArrayStringsAreEqual(string[] word1, string[] word2) {
string s1 = string.Concat(word1);
string s2 = string.Concat(word2);
return s1 == s2;
}
public static void Main(string[] args) {
string[] word1 = {"abc", "d", "defg"};
string[] word2 = {"abcddefg"};
Console.WriteLine(ArrayStringsAreEqual(word1, word2));
}
}Using Python, we leverage the join method to concatenate list elements into strings. The resultant strings are then directly compared using the equality operator.
This solution has a time complexity of O(n) and a space complexity of O(n) due to the temporary string storage.
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.
def arrayStringsAreEqual(word1, word2):
i = j = w1 = w2 = 0
while w1 < len(word1) and w2 < len(word2):
if word1[w1][i] != word2[w2][j]:
return False
i += 1
if i == len(word1[w1]):
i = 0
w1 += 1
j += 1
if j == len(word2[w2]):
j = 0
w2 += 1
return w1 == len(word1) and w2 == len(word2)
word1 = ["abc", "d", "defg"]
word2 = ["abcddefg"]
print(arrayStringsAreEqual(word1, word2))public class Main {
public static boolean arrayStringsAreEqual(String[] word1, String[] word2) {
int i = 0, j = 0, w1 = 0, w2 = 0;
while (w1 < word1.length && w2 < word2.length) {
if (word1[w1].charAt(i) != word2[w2].charAt(j)) return false;
if (++i == word1[w1].length()) { i = 0; w1++; }
if (++j == word2[w2].length()) { j = 0; w2++; }
}
return w1 == word1.length && w2 == word2.length;
}
public static void main(String[] args) {
String[] word1 = {"abc", "d", "defg"};
String[] word2 = {"abcddefg"};
System.out.println(arrayStringsAreEqual(word1, word2));
}
}#include <iostream>
#include <vector>
using namespace std;
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
int i = 0, j = 0, w1 = 0, w2 = 0;
while (w1 < word1.size() && w2 < word2.size()) {
if (word1[w1][i] != word2[w2][j]) return false;
if (++i == word1[w1].length()) { i = 0; w1++; }
if (++j == word2[w2].length()) { j = 0; w2++; }
}
return w1 == word1.size() && w2 == word2.size();
}
int main() {
vector<string> word1 = {"abc", "d", "defg"};
vector<string> word2 = {"abcddefg"};
cout << (arrayStringsAreEqual(word1, word2) ? "true" : "false") << endl;
return 0;
}function arrayStringsAreEqual(word1, word2) {
let i = 0, j = 0, w1 = 0, w2 = 0;
while (w1 < word1.length && w2 < word2.length) {
if (word1[w1][i] !== word2[w2][j]) return false;
if (++i === word1[w1].length) { i = 0; w1++; }
if (++j === word2[w2].length) { j = 0; w2++; }
}
return w1 === word1.length && w2 === word2.length;
}
const word1 = ["abc", "d", "defg"];
const word2 = ["abcddefg"];
console.log(arrayStringsAreEqual(word1, word2));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool arrayStringsAreEqual(char ** word1, int word1Size, char ** word2, int word2Size){
int i = 0, j = 0, w1 = 0, w2 = 0;
while (w1 < word1Size && w2 < word2Size) {
if (word1[w1][i] != word2[w2][j]) {
return false;
}
if (++i == strlen(word1[w1])) {
i = 0; w1++;
}
if (++j == strlen(word2[w2])) {
j = 0; w2++;
}
}
return w1 == word1Size && w2 == word2Size;
}
int main() {
char *word1[] = {"abc", "d", "defg"};
char *word2[] = {"abcddefg"};
printf("%s\n", arrayStringsAreEqual(word1, 3, word2, 1) ? "true" : "false");
return 0;
}using System;
public class Solution {
public static bool ArrayStringsAreEqual(string[] word1, string[] word2) {
int i = 0, j = 0, w1 = 0, w2 = 0;
while (w1 < word1.Length && w2 < word2.Length) {
if (word1[w1][i] != word2[w2][j]) return false;
if (++i == word1[w1].Length) { i = 0; w1++; }
if (++j == word2[w2].Length) { j = 0; w2++; }
}
return w1 == word1.Length && w2 == word2.Length;
}
public static void Main(string[] args) {
string[] word1 = {"abc", "d", "defg"};
string[] word2 = {"abcddefg"};
Console.WriteLine(ArrayStringsAreEqual(word1, word2));
}
}Within Python, the two-pointer technique efficiently traverses both arrays in tandem, avoiding intermediate string operations while maintaining fidelity in comparison.
This implementation measures at O(n) time and O(1) space, requiring no extra allocations beyond initial index-holding 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.
function arrayStringsAreEqual(word1: string[], word2: string[]): boolean {
return word1.join('') === word2.join('');
}func arrayStringsAreEqual(word1 []string, word2 []string) bool {
return strings.Join(word1, "") == strings.Join(word2, "")
}impl Solution {
pub fn array_strings_are_equal(word1: Vec<String>, word2: Vec<String>) -> bool {
word1.join("") == word2.join("")
}
}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.
function arrayStringsAreEqual(word1: string[], word2: string[]): boolean {
let [i, j, x, y] = [0, 0, 0, 0];
while (i < word1.length && j < word2.length) {
if (word1[i][x++] !== word2[j][y++]) {
return false;
}
if (x === word1[i].length) {
x = 0;
++i;
}
if (y === word2[j].length) {
y = 0;
++j;
}
}
return i === word1.length && j === word2.length;
}func arrayStringsAreEqual(word1 []string, word2 []string) bool {
var i, j, x, y int
for i < len(word1) && j < len(word2) {
if word1[i][x] != word2[j][y] {
return false
}
x, y = x+1, y+1
if x == len(word1[i]) {
x, i = 0, i+1
}
if y == len(word2[j]) {
y, j = 0, j+1
}
}
return i == len(word1) && j == len(word2)
}impl Solution {
pub fn array_strings_are_equal(word1: Vec<String>, word2: Vec<String>) -> bool {
let (n, m) = (word1.len(), word2.len());
let (mut i, mut j, mut x, mut y) = (0, 0, 0, 0);
while i < n && j < m {
if word1[i].as_bytes()[x] != word2[j].as_bytes()[y] {
return false;
}
x += 1;
y += 1;
if x == word1[i].len() {
x = 0;
i += 1;
}
if y == word2[j].len() {
y = 0;
j += 1;
}
}
i == n && j == m
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| String Concatenation Approach | This solution has a time complexity of O(n) and a space complexity of O(n) due to the temporary string storage. |
| Two-Pointer Approach | This implementation measures at O(n) time and O(1) space, requiring no extra allocations beyond initial index-holding variables. |
| String Concatenation | – |
| Direct Traversal | – |
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. |
Frequently asked questions
Is Check If Two String Arrays are Equivalent easy or hard?
The problem is classified as Easy on LeetCode with a high acceptance rate around 85%. The core challenge is recognizing that multiple strings can represent a single logical string and implementing a clean comparison strategy.
Check If Two String Arrays are Equivalent Python/Java solution
In Python or Java, the simplest implementation concatenates the arrays using join operations and compares the resulting strings. The optimized implementation maintains indices for both arrays and compares characters directly to avoid building intermediate strings while still achieving O(n) runtime.
How to solve Check If Two String Arrays are Equivalent in O(n)?
Traverse both arrays using two pointers that track the current string index and character position. Compare characters one by one and advance pointers accordingly. When a string ends, move to the next string in that array. If all characters match and both arrays finish simultaneously, the arrays represent the same string.
What is the best approach for Check If Two String Arrays are Equivalent?
The two-pointer character comparison approach is the most efficient solution. It iterates through both string arrays character by character without building full concatenated strings. This achieves O(n) time complexity and O(1) extra space, making it the preferred method in technical interviews.
Is Check If Two String Arrays are Equivalent asked at Google/Amazon/Meta?
Problems involving string comparison and pointer traversal frequently appear in interviews at companies like Amazon, Google, and Meta. This specific problem tests understanding of string handling, array traversal, and memory optimization, which are common interview themes.
What data structure is used in Check If Two String Arrays are Equivalent?
The problem primarily uses arrays of strings and sequential character traversal. The optimized solution relies on pointer indices rather than additional data structures, making it a lightweight algorithm focused on string processing.
What is the time complexity of Check If Two String Arrays are Equivalent?
The optimal solution runs in O(n) time, where n is the total number of characters across both arrays. Each character is visited exactly once during comparison. The concatenation method also runs in O(n) time but uses additional O(n) memory for the constructed strings.