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] and word2[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.
PythonJavaC++GoTypeScriptRustC
class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
return ''.join(word1) == ''.join(word2)(code-box)
class Solution {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
return String.join("", word1).equals(String.join("", word2));
}
}(code-box)
class Solution {
public:
bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
return reduce(word1.cbegin(), word1.cend()) == reduce(word2.cbegin(), word2.cend());
}
};(code-box)
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
return strings.Join(word1, "") == strings.Join(word2, "")
}(code-box)
function arrayStringsAreEqual(word1: string[], word2: string[]): boolean {
return word1.join('') === word2.join('');
}(code-box)
impl Solution {
pub fn array_strings_are_equal(word1: Vec<String>, word2: Vec<String>) -> bool {
word1.join("") == word2.join("")
}
}(code-box)
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;
}(code-box)
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.
PythonJavaC++GoTypeScriptRust
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)(code-box)
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;
}
}(code-box)
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();
}
};(code-box)
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)
}(code-box)
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;
}(code-box)
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
}
}(code-box)
