0%

LeetCode 1662. Check If Two String Arrays are Equivalent

Posted on Edited on In

题目

原题在此
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 <= 103
  • 1 <= word1[i].length, word2[i].length <= 103
  • 1 <= sum(word1[i].length), sum(word2[i].length) <= 103
  • word1[i] and word2[i] consist of lowercase letters.

解析

把string拼起来再看它们是否相等是最简单的,但会使用额外空间.
也可以用4个指针遍历两个二维数组,达到$O(1)$空间复杂度.
甚至可以写一个Iterator,实现hasNext()和next().

代码

1
2
3
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
    return (String.join("",  word1)).equals(String.join("",  word2));
}
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 wp1=0, wp2 = 0, sp1=0, sp2=0;
        while(wp1 < word1.size() && wp2 < word2.size() && word1[wp1][sp1] == word2[wp2][sp2]) {
            if(++sp1 == word1[wp1].size()) {
                wp1++;
                sp1 = 0;
            }
            if(++sp2 == word2[wp2].size()) {
                wp2++;
                sp2 = 0;
            }
        }
        return wp1 == word1.size() && wp2 == word2.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
    it1, it2 := iterator{words:word1}, iterator{words:word2}
    for it1.hasNext() && it2.hasNext() {
        if it1.next() != it2.next() {
            return false
        }
    }
    return it1.hasNext() == it2.hasNext()
}

type iterator struct {
    words []string
    currentWord int
    currentIndex int
}

func (i *iterator) hasNext() bool {
    if i.currentWord < len(i.words) {
        if i.currentIndex < len(i.words[i.currentWord]) {
            return true
        } else {
            i.currentWord++
            i.currentIndex = 0
            return i.hasNext()
        }
    }
    return false
}

func (i *iterator) next() byte {
    var result byte
    if !i.hasNext() {
        return result
    }
    result = i.words[i.currentWord][i.currentIndex]
    i.currentIndex++
    return result
}