题目描述
思路解析动画文字版
记牢这句话:数组怎么切不重要,先各自拼成完整字符串,再整串对整串地比。下面每一帧都在做拼接或者比对这两件事。
总览 · 两行待拼：先看舞台。上面这一行准备放 word1 拼出来的字符串 s1,下面这一行准备放 word2 拼出来的字符串 s2。右边面板列着两个数组各自由哪些词组成。现在两行都还是灰的,代表都没正式拼好。接下来我先把上行 s1 一段一段拼出来,再拼下行 s2,最后逐列比对。
拼 s1 · 接上 "ab"：把 word1 的第 0 个元素 "ab" 接到上行后面,它有 2 个字符,依次放进第 0 到第 1 格。橙色就是这一帧刚接上的部分,灰蓝色是之前已经拼好的。到这里上行 s1 已经是 "ab"。
拼 s1 · 接上 "c"：把 word1 的第 1 个元素 "c" 接到上行后面,它只有一个字符,放进第 2 格。橙色就是这一帧刚接上的部分,灰蓝色是之前已经拼好的。到这里上行 s1 已经是 "abc"。
拼 s1 · 接上 "de"：把 word1 的第 2 个元素 "de" 接到上行后面,它有 2 个字符,依次放进第 3 到第 4 格。橙色就是这一帧刚接上的部分,灰蓝色是之前已经拼好的。到这里上行 s1 已经是 "abcde"。
s1 拼好 · "abcde"：上行三段都接完了,word1 = ["ab", "c", "de"] 顺次相连拼成了完整的 s1 = "abcde",一共 5 个字符。注意拼接只看顺序、不看原来怎么分段。上行就位,下面去拼下行 s2。
拼 s2 · 接上 "a"：换下行。把 word2 的第 0 个元素 "a" 接到下行后面,它只有一个字符,放进第 0 格。橙色是本帧刚接上的部分。到这里下行 s2 已经是 "a"。你会发现 word2 的分段方式和 word1 完全不同,但拼出来的样子越来越像。
拼 s2 · 接上 "bcde"：换下行。把 word2 的第 1 个元素 "bcde" 接到下行后面,它有 4 个字符,依次放进第 1 到第 4 格。橙色是本帧刚接上的部分。到这里下行 s2 已经是 "abcde"。你会发现 word2 的分段方式和 word1 完全不同,但拼出来的样子越来越像。
s2 拼好 · "abcde"：下行也拼完了,word2 = ["a", "bcde"] 拼成了 s2 = "abcde"。现在两行都摆好:上行 s1 = "abcde",下行 s2 = "abcde"。一个数组切成三段、一个切成两段,拼出来居然长得一模一样,到底是不是真的一样,得一列一列对照着验。
先比长度：正式比之前先看长度。s1 有 5 个字符,s2 也有 5 个字符,长度相等。这一步很关键:如果两个串长度都不一样,那根本不可能相等,可以立刻返回 false,连逐字符都省了。这里长度相同,说明有得比,下面从第 0 列开始一列一列地对字符。
比第 0 列 · 对照：把目光对到第 0 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 0 个字符 "a",下行这一格是 s2 的第 0 个字符 "a"。它俩相不相同?下一帧揭晓。左边已经比过的列会标成绿色,绿色越铺越长就说明前面都对得上。
第 0 列 · 相同："a" 和 "a" 是同一个字符,这一列对上了,两格一起变绿。已经对上 1 列,还差 4 列,继续往右挪到第 1 列。
比第 1 列 · 对照：把目光对到第 1 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 1 个字符 "b",下行这一格是 s2 的第 1 个字符 "b"。它俩相不相同?下一帧揭晓。前面 1 列已经全绿,代表都已对上。
第 1 列 · 相同："b" 和 "b" 是同一个字符,这一列对上了,两格一起变绿。已经对上 2 列,还差 3 列,继续往右挪到第 2 列。
比第 2 列 · 对照：把目光对到第 2 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 2 个字符 "c",下行这一格是 s2 的第 2 个字符 "c"。它俩相不相同?下一帧揭晓。前面 2 列已经全绿,代表都已对上。
第 2 列 · 相同："c" 和 "c" 是同一个字符,这一列对上了,两格一起变绿。已经对上 3 列,还差 2 列,继续往右挪到第 3 列。
比第 3 列 · 对照：把目光对到第 3 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 3 个字符 "d",下行这一格是 s2 的第 3 个字符 "d"。它俩相不相同?下一帧揭晓。前面 3 列已经全绿,代表都已对上。
第 3 列 · 相同："d" 和 "d" 是同一个字符,这一列对上了,两格一起变绿。已经对上 4 列,还差 1 列,继续往右挪到第 4 列。
比第 4 列 · 对照：把目光对到第 4 列,紫色高亮的就是要比的这一对。上行这一格是 s1 的第 4 个字符 "e",下行这一格是 s2 的第 4 个字符 "e"。它俩相不相同?下一帧揭晓。前面 4 列已经全绿,代表都已对上。
第 4 列 · 相同："e" 和 "e" 是同一个字符,这一列对上了,两格一起变绿。这是最后一列,也对上了,全部 5 列都通过。
结论 · true：五列全绿,意味着 s1 和 s2 长度相等、而且每一个字符都对得上,这两个字符串完全相同,所以返回 true。回头看,word1 切成三段、word2 切成两段,切法天差地别,可一旦拼成整串再比,答案清清楚楚。
回放 · 答案 true：把整个过程回放一遍:先把 word1 顺次拼成 s1 = "abcde",再把 word2 顺次拼成 s2 = "abcde",然后比长度发现都是 5,再一列一列比字符,五列全部相同。结论就是两个数组表示的字符串相等,返回 true。整个过程把每个字符只碰了常数次,既直观又高效。
边界先想清:内容差一位就 false、长度不等可直接 false、分段方式不同但拼成整串相同就返回 true。
面试重点:直接拼接比较一定对、双指针流式比较可做到 O(1) 空间还能提前停、它是把切分过的输入先归一化再比较的套路。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool: return ''.join(word1) == ''.join(word2)复杂度
- 时间：O(n)，n 是两个数组里所有字符的总数。拼接要把每个字符各扫一遍是 O(n),比较两个串再扫一遍也是 O(n),合计还是 O(n)
- 空间：O(n)，这套解法把两个数组各自拼成一个完整字符串,峰值要同时存住这两个长度合计为 O(n) 的串,所以额外空间是 O(n)。如果改用两个指针在原数组上流式逐字符比较、不预先拼接,额外空间可以降到 O(1)
易错点
面试追问把动画讲成自己的话
追问这道题最直接的写法是什么,为什么一定正确?
追问面试官追问能不能不额外建字符串、做到 O(1) 空间?
追问这类题属于什么套路,以后怎么认?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
基于排列构建数组
LeetCode 1920 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题