1662. Check If Two String Arrays are Equivalent
Description
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.
Solutions
Solution 1: 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.
Python3
class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
return ''.join(word1) == ''.join(word2)
Java
class Solution {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
return String.join("", word1).equals(String.join("", word2));
}
}
C++
class Solution {
public:
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
return reduce(word1.cbegin(), word1.cend()) == reduce(word2.cbegin(), word2.cend());
}
};
Go
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
return strings.Join(word1, "") == strings.Join(word2, "")
}
TypeScript
function arrayStringsAreEqual(word1: string[], word2: string[]): boolean {
return word1.join('') === word2.join('');
}
Rust
impl Solution {
pub fn array_strings_are_equal(word1: Vec<String>, word2: Vec<String>) -> bool {
word1.join("") == word2.join("")
}
}
C
bool arrayStringsAreEqual(char** word1, int word1Size, char** word2, int word2Size) {
int i = 0;
int j = 0;
int x = 0;
int y = 0;
while (i < word1Size && j < word2Size) {
if (word1[i][x++] != word2[j][y++]) {
return 0;
}
if (word1[i][x] == '\0') {
x = 0;
i++;
}
if (word2[j][y] == '\0') {
y = 0;
j++;
}
}
return i == word1Size && j == word2Size;
}
Solution 2: 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.
Python3
class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
i = j = x = y = 0
while i < len(word1) and 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) and j == len(word2)
Java
class Solution {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
int i = 0, j = 0;
int x = 0, y = 0;
while (i < word1.length && j < word2.length) {
if (word1[i].charAt(x++) != word2[j].charAt(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;
}
}
C++
class Solution {
public:
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
int i = 0, j = 0, x = 0, y = 0;
while (i < word1.size() && j < word2.size()) {
if (word1[i][x++] != word2[j][y++]) return false;
if (x == word1[i].size()) x = 0, i++;
if (y == word2[j].size()) y = 0, j++;
}
return i == word1.size() && j == word2.size();
}
};
Go
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)
}
TypeScript
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;
}
Rust
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
}
}