LeetCode 1662: Check If Two String Arrays are Equivalent (Two-Pointer Streaming Comparison)
LeetCode 1662StringTwo PointersSimulationToday we solve LeetCode 1662 - Check If Two String Arrays are Equivalent.
Source: https://leetcode.com/problems/check-if-two-string-arrays-are-equivalent/
English
Problem Summary
Given two string arrays word1 and word2, each array represents one concatenated string. Return true if both final strings are equal, otherwise false.
Key Insight
Do not build the full concatenated strings. We can compare characters in a streaming way using two pointers:
- one pointer for current word index, one for char index in word1
- one pointer for current word index, one for char index in word2
Algorithm
1) Initialize i, p for word1, and j, q for word2.
2) While both arrays still have characters, compare word1[i][p] and word2[j][q].
3) Move pointers forward; when a word ends, move to next word and reset char pointer to 0.
4) At the end, both sides must be consumed exactly.
Complexity Analysis
Time: O(totalChars).
Space: O(1) extra space.
Common Pitfalls
- Forgetting to advance to the next word when char pointer reaches word length.
- Returning true too early before confirming both sides are fully consumed.
- Building giant strings unnecessarily.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
int i = 0, p = 0;
int j = 0, q = 0;
while (i < word1.length && j < word2.length) {
if (word1[i].charAt(p) != word2[j].charAt(q)) {
return false;
}
p++;
if (p == word1[i].length()) {
i++;
p = 0;
}
q++;
if (q == word2[j].length()) {
j++;
q = 0;
}
}
return i == word1.length && j == word2.length;
}
}func arrayStringsAreEqual(word1 []string, word2 []string) bool {
i, p := 0, 0
j, q := 0, 0
for i < len(word1) && j < len(word2) {
if word1[i][p] != word2[j][q] {
return false
}
p++
if p == len(word1[i]) {
i++
p = 0
}
q++
if q == len(word2[j]) {
j++
q = 0
}
}
return i == len(word1) && j == len(word2)
}class Solution {
public:
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
int i = 0, p = 0;
int j = 0, q = 0;
while (i < (int)word1.size() && j < (int)word2.size()) {
if (word1[i][p] != word2[j][q]) {
return false;
}
++p;
if (p == (int)word1[i].size()) {
++i;
p = 0;
}
++q;
if (q == (int)word2[j].size()) {
++j;
q = 0;
}
}
return i == (int)word1.size() && j == (int)word2.size();
}
};class Solution:
def arrayStringsAreEqual(self, word1: list[str], word2: list[str]) -> bool:
i = p = 0
j = q = 0
while i < len(word1) and j < len(word2):
if word1[i][p] != word2[j][q]:
return False
p += 1
if p == len(word1[i]):
i += 1
p = 0
q += 1
if q == len(word2[j]):
j += 1
q = 0
return i == len(word1) and j == len(word2)var arrayStringsAreEqual = function(word1, word2) {
let i = 0, p = 0;
let j = 0, q = 0;
while (i < word1.length && j < word2.length) {
if (word1[i][p] !== word2[j][q]) {
return false;
}
p++;
if (p === word1[i].length) {
i++;
p = 0;
}
q++;
if (q === word2[j].length) {
j++;
q = 0;
}
}
return i === word1.length && j === word2.length;
};中文
题目概述
给定两个字符串数组 word1 和 word2，每个数组拼接后会形成一个完整字符串。判断两个拼接结果是否相同。
核心思路
不需要真的把所有字符串拼起来。使用“双数组流式比较”：
- i,p 指向 word1 的“第 i 个字符串、第 p 个字符”
- j,q 指向 word2 的“第 j 个字符串、第 q 个字符”
每次比较当前字符，相等就同步向前推进。
算法步骤
1）初始化四个指针 i,p,j,q。
2）循环比较当前字符，不同立即返回 false。
3）字符指针前进；若到达当前字符串末尾，则切到下一个字符串并把字符指针归零。
4）循环结束后，必须两个数组都刚好消费完，才返回 true。
复杂度分析
时间复杂度：O(总字符数)。
空间复杂度：O(1) 额外空间。
常见陷阱
- 字符下标走到末尾后忘记切换到下一个单词。
- 只要一边结束就直接返回 true，忽略另一边可能还有剩余字符。
- 先整体拼接再比较，导致多余空间开销。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
int i = 0, p = 0;
int j = 0, q = 0;
while (i < word1.length && j < word2.length) {
if (word1[i].charAt(p) != word2[j].charAt(q)) {
return false;
}
p++;
if (p == word1[i].length()) {
i++;
p = 0;
}
q++;
if (q == word2[j].length()) {
j++;
q = 0;
}
}
return i == word1.length && j == word2.length;
}
}func arrayStringsAreEqual(word1 []string, word2 []string) bool {
i, p := 0, 0
j, q := 0, 0
for i < len(word1) && j < len(word2) {
if word1[i][p] != word2[j][q] {
return false
}
p++
if p == len(word1[i]) {
i++
p = 0
}
q++
if q == len(word2[j]) {
j++
q = 0
}
}
return i == len(word1) && j == len(word2)
}class Solution {
public:
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
int i = 0, p = 0;
int j = 0, q = 0;
while (i < (int)word1.size() && j < (int)word2.size()) {
if (word1[i][p] != word2[j][q]) {
return false;
}
++p;
if (p == (int)word1[i].size()) {
++i;
p = 0;
}
++q;
if (q == (int)word2[j].size()) {
++j;
q = 0;
}
}
return i == (int)word1.size() && j == (int)word2.size();
}
};class Solution:
def arrayStringsAreEqual(self, word1: list[str], word2: list[str]) -> bool:
i = p = 0
j = q = 0
while i < len(word1) and j < len(word2):
if word1[i][p] != word2[j][q]:
return False
p += 1
if p == len(word1[i]):
i += 1
p = 0
q += 1
if q == len(word2[j]):
j += 1
q = 0
return i == len(word1) and j == len(word2)var arrayStringsAreEqual = function(word1, word2) {
let i = 0, p = 0;
let j = 0, q = 0;
while (i < word1.length && j < word2.length) {
if (word1[i][p] !== word2[j][q]) {
return false;
}
p++;
if (p === word1[i].length) {
i++;
p = 0;
}
q++;
if (q === word2[j].length) {
j++;
q = 0;
}
}
return i === word1.length && j === word2.length;
};
Comments