Given two string arrays word1
and word2
, returntrue
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 <= 103
1 <= word1[i].length, word2[i].length <= 103
1 <= sum(word1[i].length), sum(word2[i].length) <= 103
word1[i]
andword2[i]
consist of lowercase letters.
Solution1: Construct the string
Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)
C++
1 2 3 4 5 6 7 8 9 |
class Solution { public: bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) { string s1, s2; for (const string& w1 : word1) s1 += w1; for (const string& w2 : word2) s2 += w2; return s1 == s2; } }; |
Solution 2: Pointers
Time complexity: O(l1 + l2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) { int i1 = 0, j1 = 0; int i2 = 0, j2 = 0; while (i1 < word1.size() || i2 < word2.size()) { char c1 = i1 < word1.size() ? word1[i1][j1++] : '\0'; char c2 = i2 < word2.size() ? word2[i2][j2++] : '\0'; if (c1 != c2) return false; if (i1 < word1.size() && j1 == word1[i1].length()) ++i1, j1 = 0; if (i2 < word2.size() && j2 == word2[i2].length()) ++i2, j2 = 0; } return true; } }; |