检查两个字符串数组是否相等 图解题解

这道题到底在问什么

输入

word1 = ["ab", "c"], word2 = ["a", "bc"]

输出

true(两边都拼成 "abc")

输入

word1 = ["a", "cb"], word2 = ["ab", "c"]

输出

false("acb" 与 "abc" 第二个字符就不同)

输入

word1 = ["abc", "d", "defg"], word2 = ["abcddefg"]

输出

true(都拼成 "abcddefg",一个分三段一个只一段)

最优解：一步一步想明白

1. 3记牢这句话:数组怎么切不重要,先各自拼成完整字符串,再整串对整串地比。下面每一帧都在做拼接或者比对这两件事。
2. 4先看舞台。上面这一行准备放 word1 拼出来的字符串 s1,下面这一行准备放 word2 拼出来的字符串 s2。右边面板列着两个数组各自由哪些词组成。现在两行都还是灰的,代表都没正式拼好。接下来我先把上行 s1 一段一段拼出来,再拼下行 s2,最后逐列比对。
3. 5把 word1 的第 0 个元素 "ab" 接到上行后面,它有 2 个字符,依次放进第 0 到第 1 格。橙色就是这一帧刚接上的部分,灰蓝色是之前已经拼好的。到这里上行 s1 已经是 "ab"。
4. 6把 word1 的第 1 个元素 "c" 接到上行后面,它只有一个字符,放进第 2 格。橙色就是这一帧刚接上的部分,灰蓝色是之前已经拼好的。到这里上行 s1 已经是 "abc"。
5. 7把 word1 的第 2 个元素 "de" 接到上行后面,它有 2 个字符,依次放进第 3 到第 4 格。橙色就是这一帧刚接上的部分,灰蓝色是之前已经拼好的。到这里上行 s1 已经是 "abcde"。
6. 8上行三段都接完了,word1 = ["ab", "c", "de"] 顺次相连拼成了完整的 s1 = "abcde",一共 5 个字符。注意拼接只看顺序、不看原来怎么分段。上行就位,下面去拼下行 s2。
7. 9换下行。把 word2 的第 0 个元素 "a" 接到下行后面,它只有一个字符,放进第 0 格。橙色是本帧刚接上的部分。到这里下行 s2 已经是 "a"。你会发现 word2 的分段方式和 word1 完全不同,但拼出来的样子越来越像。
8. 10换下行。把 word2 的第 1 个元素 "bcde" 接到下行后面,它有 4 个字符,依次放进第 1 到第 4 格。橙色是本帧刚接上的部分。到这里下行 s2 已经是 "abcde"。你会发现 word2 的分段方式和 word1 完全不同,但拼出来的样子越来越像。
9. 11下行也拼完了,word2 = ["a", "bcde"] 拼成了 s2 = "abcde"。现在两行都摆好:上行 s1 = "abcde",下行 s2 = "abcde"。一个数组切成三段、一个切成两段,拼出来居然长得一模一样,到底是不是真的一样,得一列一列对照着验。
10. 12正式比之前先看长度。s1 有 5 个字符,s2 也有 5 个字符,长度相等。这一步很关键:如果两个串长度都不一样,那根本不可能相等,可以立刻返回 false,连逐字符都省了。这里长度相同,说明有得比,下面从第 0 列开始一列一列地对字符。
11. 13把目光对到第 0 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 0 个字符 "a",下行这一格是 s2 的第 0 个字符 "a"。它俩相不相同?下一帧揭晓。左边已经比过的列会标成绿色,绿色越铺越长就说明前面都对得上。
12. 14"a" 和 "a" 是同一个字符,这一列对上了,两格一起变绿。已经对上 1 列,还差 4 列,继续往右挪到第 1 列。
13. 15把目光对到第 1 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 1 个字符 "b",下行这一格是 s2 的第 1 个字符 "b"。它俩相不相同?下一帧揭晓。前面 1 列已经全绿,代表都已对上。
14. 16"b" 和 "b" 是同一个字符,这一列对上了,两格一起变绿。已经对上 2 列,还差 3 列,继续往右挪到第 2 列。
15. 17把目光对到第 2 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 2 个字符 "c",下行这一格是 s2 的第 2 个字符 "c"。它俩相不相同?下一帧揭晓。前面 2 列已经全绿,代表都已对上。
16. 18"c" 和 "c" 是同一个字符,这一列对上了,两格一起变绿。已经对上 3 列,还差 2 列,继续往右挪到第 3 列。
17. 19把目光对到第 3 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 3 个字符 "d",下行这一格是 s2 的第 3 个字符 "d"。它俩相不相同?下一帧揭晓。前面 3 列已经全绿,代表都已对上。
18. 20"d" 和 "d" 是同一个字符,这一列对上了,两格一起变绿。已经对上 4 列,还差 1 列,继续往右挪到第 4 列。
19. 21把目光对到第 4 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 4 个字符 "e",下行这一格是 s2 的第 4 个字符 "e"。它俩相不相同?下一帧揭晓。前面 4 列已经全绿,代表都已对上。
20. 22"e" 和 "e" 是同一个字符,这一列对上了,两格一起变绿。这是最后一列,也对上了,全部 5 列都通过。
21. 23五列全绿,意味着 s1 和 s2 长度相等、而且每一个字符都对得上,这两个字符串完全相同,所以返回 true。回头看,word1 切成三段、word2 切成两段,切法天差地别,可一旦拼成整串再比,答案清清楚楚。
22. 24把整个过程回放一遍:先把 word1 顺次拼成 s1 = "abcde",再把 word2 顺次拼成 s2 = "abcde",然后比长度发现都是 5,再一列一列比字符,五列全部相同。结论就是两个数组表示的字符串相等,返回 true。整个过程把每个字符只碰了常数次,既直观又高效。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        return ''.join(word1) == ''.join(word2)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        string s1, s2;
        for (const string& w : word1) s1 += w;
        for (const string& w : word2) s2 += w;
        return s1 == s2;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        return String.join("", word1).equals(String.join("", word2));
    }
}

复杂度

面试官可能追问