题目描述
思路解析动画文字版
记住这条「逐位对齐比 → 失配就整体右移、从头再比」,下面每一帧都在套它。
文本一字排开,模式串 "ababd" 像一把尺子先放在最左边(下标 0 对齐)。接下来从尺子第一位开始,一格一格往右对比。
尺子放在起点 0:模式串第 0 位 'a' 对上了文本第 0 格的 'a',这一位相等(标绿),继续往后比下一位。
尺子放在起点 0:模式串第 1 位 'b' 对上了文本第 1 格的 'b',这一位相等(标绿),继续往后比下一位。
尺子放在起点 0:模式串第 2 位 'a' 对上了文本第 2 格的 'a',这一位相等(标绿),继续往后比下一位。
尺子放在起点 0:模式串第 3 位 'b' 对上了文本第 3 格的 'b',这一位相等(标绿),继续往后比下一位。
尺子放在起点 0:模式串第 4 位 'd' 撞上文本第 4 格的 'c',两者不等(标红)。这个起点废了。
既然起点 0 比不通,就把整把尺子向右挪一格到起点 1,前面对上的都作废、绿色清空,重新从模式串第 0 位开始对比。
尺子放在起点 1:模式串第 0 位 'a' 撞上文本第 1 格的 'b',两者不等(标红)。这个起点废了。
既然起点 1 比不通,就把整把尺子向右挪一格到起点 2,前面对上的都作废、绿色清空,重新从模式串第 0 位开始对比。
尺子放在起点 2:模式串第 0 位 'a' 对上了文本第 2 格的 'a',这一位相等(标绿),继续往后比下一位。
尺子放在起点 2:模式串第 1 位 'b' 对上了文本第 3 格的 'b',这一位相等(标绿),继续往后比下一位。
尺子放在起点 2:模式串第 2 位 'a' 撞上文本第 4 格的 'c',两者不等(标红)。这个起点废了。
既然起点 2 比不通,就把整把尺子向右挪一格到起点 3,前面对上的都作废、绿色清空,重新从模式串第 0 位开始对比。
尺子放在起点 3:模式串第 0 位 'a' 撞上文本第 3 格的 'b',两者不等(标红)。这个起点废了。
既然起点 3 比不通,就把整把尺子向右挪一格到起点 4,前面对上的都作废、绿色清空,重新从模式串第 0 位开始对比。
尺子放在起点 4:模式串第 0 位 'a' 撞上文本第 4 格的 'c',两者不等(标红)。这个起点废了。
既然起点 4 比不通,就把整把尺子向右挪一格到起点 5,前面对上的都作废、绿色清空,重新从模式串第 0 位开始对比。
尺子放在起点 5:模式串第 0 位 'a' 对上了文本第 5 格的 'a',这一位相等(标绿),继续往后比下一位。
尺子放在起点 5:模式串第 1 位 'b' 对上了文本第 6 格的 'b',这一位相等(标绿),继续往后比下一位。
尺子放在起点 5:模式串第 2 位 'a' 对上了文本第 7 格的 'a',这一位相等(标绿),继续往后比下一位。
尺子放在起点 5:模式串第 3 位 'b' 对上了文本第 8 格的 'b',这一位相等(标绿),继续往后比下一位。
尺子放在起点 5:模式串第 4 位 'd' 对上了文本第 9 格的 'd',这一位相等(标绿),继续往后比下一位。
从起点 5 一路比到模式串最后一位,全部对上(整段标绿)!这就是 "ababd" 第一次出现的位置,答案返回起始下标 5。
边界先想清:开头即中、全程差一点(部分匹配但最终 -1)、以及最短输入。
三个高频追问:最坏输入、KMP 优化思路、以及何时直接用库函数。
参考代码
def strStr(haystack: str, needle: str) -> int: n, m = len(haystack), len(needle) for i in range(n - m + 1): # 枚举每个起点 j = 0 while j < m and haystack[i + j] == needle[j]: j += 1 # 这一位对上,继续 if j == m: # 全部对上 return i return -1复杂度
- 时间:O(n·m),最坏每个起点都要比 m 位,起点有 n−m+1 个
- 空间:O(1),只用 i、j 两个下标,不额外开空间
易错点
面试追问把动画讲成自己的话
追问朴素法最坏会有多慢?什么输入能卡到 O(n·m)?
追问怎么把它优化到线性 O(n+m)?
追问为什么很多场景直接用库函数 indexOf / find 就够了?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
轮转数组
LeetCode 189 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题