LeetCode 28 找出字符串中第一个匹配项的下标LeetCode 28 找出字符串中第一个匹配项的下标一、前置知识for ... else二、我的第一反应先找可能的起点再逐个字符比较三、第一个问题break 以后还是执行了 return i方法一使用 for ... else方法二自己用变量记录四、第二个问题i 不能一直走到 haystack 最后五、完整代码for ... else六、使用 matched 的写法七、还能怎么优化 -- KMPKMP 是怎么利用前面信息的lps 是什么先构造 lps如果不相同为什么不能直接把 length 变成 0如果已经退到 length 0 还是不相同呢再使用 lps 进行匹配完整代码LeetCode 28 找出字符串中第一个匹配项的下标LeetCode 28 找出字符串中第一个匹配项的下标题目给出两个字符串haystack和needle要求在haystack中找到needle第一次完整出现的位置。如果找不到就返回-1。例如haystack sadbutsad needle sadsad分别出现在下标0和6题目要求的是第一个匹配位置所以返回0所以, 这道题最直接的想法就是把haystack中每一个可能的位置都当成起点然后从这个位置开始一个字符一个字符和needle比较。一、前置知识for ... else在 Python 中for可以和else搭配forxinnums:if某个条件:breakelse:# for 没有被 break 打断时执行这里的else不是像往常一样和if配对而是和for配对。规则是for 正常遍历结束 → 执行 else for 中途遇到 break → 不执行 else例如forxin[1,2,3]:ifx4:breakelse:print(没有找到)整个循环都没有触发break因此最后会执行else。所以, 这种写法特别适合这样的逻辑我要检查一系列条件只要其中一个失败就break如果一直没有失败就说明全部检查通过。这正好可以用在这道字符串匹配题里。二、我的第一反应先找可能的起点再逐个字符比较我的想法是先遍历haystackforiinrange(len(haystack)):这里的i表示当前尝试把haystack[i]当作needle的起点。比如haystack sadbutsad needle sad如果i 0首先比较haystack[0] 和 needle[0]如果第一个字符都不同那当前位置肯定不可能匹配可以直接continue去尝试下一个起点。如果第一个字符相同再继续比较后面的字符forjinrange(1,len(needle)):此时可以设定haystack[i j]表示从当前起点i往后移动j位而needle[j]表示needle中对应位置的字符。所以整体思路其实就是枚举起点 i → 第一个字符不同直接换下一个起点 → 第一个字符相同继续比较后面的字符 → 中间有一个字符不同当前起点失败 → 所有字符都相同返回当前 i我最开始按照这个思路写出了classSolution:defstrStr(self,haystack:str,needle:str)-int:foriinrange(len(haystack)):ifhaystack[i]!needle[0]:continueelse:forjinrange(1,len(needle)):ifhaystack[ij]!needle[j]:breakreturnireturn-1思路本身没有问题但是这里有两个容易忽略的漏洞。三、第一个问题break以后还是执行了return i原来的代码中forjinrange(1,len(needle)):ifhaystack[ij]!needle[j]:breakreturni我原本的想法是发现字符不同 → break → 当前 i 失败但实际上break只会退出里面的for j退出以后程序会继续往下执行于是马上遇到returni所以实际逻辑变成了第一个字符相同 → 开始比较后面的字符 → 中间发现不同 → break → 还是 return i也就是说代码没有真正区分因为匹配失败而退出循环 和 因为所有字符都比较成功而结束循环这里可以有两种解决方式。方法一使用for ... else也就是前面前置知识教的:forjinrange(1,len(needle)):ifhaystack[ij]!needle[j]:breakelse:returni如果中间有字符不同就会触发break因此不会进入else只有整个for j正常结束也就是所有字符都匹配成功才会执行returni所以这里的逻辑刚好是出现不同 → break → 当前 i 失败 从头到尾都没有 break → 所有字符匹配成功 → return i方法二自己用变量记录如果不用for ... else也可以自己用一个变量记录当前起点是否匹配成功matchedTrueforjinrange(1,len(needle)):ifhaystack[ij]!needle[j]:matchedFalsebreakifmatched:returni这里的matched表示当前这个起点i到目前为止有没有发现匹配失败。可能会疑惑为什么一开始就写matchedTrue明明后面的字符还没有比较怎么就先认为匹配成功了其实, 这里不是在说“已经证明成功”而是在表示先假设当前起点可以匹配只要后面发现任何一个反例就把它改成False。因为前面已经检查过ifhaystack[i]!needle[0]:continue所以能走到matched True这里时至少第一个字符已经相同。接下来只需要检查剩余字符。例如haystack sax... needle sad i 0第一个字符s s已经通过所以先matchedTrue然后继续检查a a仍然没有发现问题matched保持True。再检查x ! d这时候终于发现当前起点不成立于是matchedFalsebreak离开内层循环后ifmatched:因为现在是False所以不会return i外层循环会继续尝试下一个起点。反过来如果整个内层循环都没有找到任何不同第 1 位相同 第 2 位相同 第 3 位相同 ……那么就没有任何地方执行matchedFalse所以matched一直保持True。这时候才说明所有需要检查的字符都通过了因此当前i确实是一个完整匹配的位置。于是ifmatched:returni就是安全的。可以把这个逻辑理解成matched True → 暂时没有发现问题 发现任何一个字符不同 → matched False 整个检查结束后还是 True → 从头到尾都没有发现问题 → 当前起点匹配成功这里还有一个很重要的细节matched True必须放在每一次新的i尝试里面。也就是说foriin...:matchedTrue每换一个新的起点都要重新开始判断。否则前一个起点失败后留下的False可能会影响下一个起点。这个方法最核心的就是matched True是“目前还没有找到失败的证据”只要出现一次不匹配就立刻改成False。两种方法本质一样for ... else → 用“有没有 break”判断是否匹配成功 matched → 自己使用布尔值保存匹配状态四、第二个问题i不能一直走到 haystack 最后原来写的是foriinrange(len(haystack)):但后面还要访问haystack[ij]所以如果i已经走得太靠后而剩余字符数量又不足以放下整个needle就可能发生数组越界。例如haystack abcde needle cdehaystack长度为 5needle长度为 3。合法起点其实只有i 0 i 1 i 2因为当i 2检查的位置是2、3、4刚好还能放下长度为 3 的needle。但如果i 3后面只剩下两个字符d e无论内容是什么都已经不可能匹配长度为 3 的needle所以这些位置根本没有必要继续尝试。因此最后一个合法起点应该是len(haystack) - len(needle)因为range的右边取不到所以应该写成foriinrange(len(haystack)-len(needle)1):这样既避免越界也直接排除了那些长度上就不可能成功的位置。五、完整代码for ... else结合上面两个问题可以写成classSolution:defstrStr(self,haystack:str,needle:str)-int:foriinrange(len(haystack)-len(needle)1):ifhaystack[i]!needle[0]:continueforjinrange(1,len(needle)):ifhaystack[ij]!needle[j]:breakelse:returnireturn-1这里可以把两个循环的职责分开理解i → 枚举 needle 可能出现的起点 j → 从这个起点开始检查 needle 中的每一个字符如果当前起点失败就让外层的i继续寻找下一个位置如果整个j循环都没有失败就直接返回当前i。六、使用matched的写法如果觉得for ... else比较陌生也可以使用matchedclassSolution:defstrStr(self,haystack:str,needle:str)-int:foriinrange(len(haystack)-len(needle)1):ifhaystack[i]!needle[0]:continuematchedTrueforjinrange(1,len(needle)):ifhaystack[ij]!needle[j]:matchedFalsebreakifmatched:returnireturn-1七、还能怎么优化 – KMP目前这套方法本质上属于暴力字符串匹配。假设haystack 长度 n needle 长度 m最多需要尝试大约n - m 1个起点而每个起点最坏需要比较m个字符所以最坏时间复杂度是O(n × m)例如haystack aaaaaaaaaaaaaaaaab needle aaaaab很多起点都会出现前面连续匹配很多个 a → 到最后才发现不同 → 换下一个起点 → 又把前面的 a 重新比较一遍这里会产生浪费匹配失败以后已经比较过的信息几乎全部丢掉了。这和前面做其他优化题时的思路很像可以继续问当前这次匹配虽然失败了但是已经匹配成功的那一部分信息能不能留给下一次使用这就会引出经典的KMPKnuth-Morris-Pratt字符串匹配算法。KMP 会提前分析needle本身的前缀和后缀关系使得匹配失败时不需要让haystack的比较位置完全退回重新开始而是利用已经得到的信息继续匹配。它可以把最坏时间复杂度从O(n × m)降低到O(n m)不过对于这道简单题来说先把现在这种“双循环逐字符匹配”的逻辑完全理解清楚已经足够。KMP 更适合作为后续字符串算法的扩展再单独学习。这里就简单说说:继续往下看KMP 真正要解决的就是既然前面已经有一部分匹配成功了那么失败以后能不能不要全部推倒重来而是利用这部分已经匹配成功的信息KMP 是怎么利用前面信息的例如haystack ababab... needle ababc从开头开始匹配haystack: a b a b a b ... needle: a b a b c ✓ ✓ ✓ ✓ ×前面的abab已经匹配成功只是比较下一个字符时出现了haystacka needle c暴力方法会把当前起点判定为失败然后换一个新的起点再从needle[0]开始比较。这样做的问题是前面已经成功比较过的abab信息全部被丢掉了。KMP 会继续观察这段已经匹配成功的abababab ^^ 前缀 ab abab ^^ 后缀 ab可以发现它的前缀ab和后缀ab是相同的。这意味着虽然完整匹配失败了但是haystack刚刚匹配过的末尾两个字符已经确定是ab而needle开头两个字符也正好是ab。所以这两个字符没有必要重新比较可以直接把needle调整到一个新的位置继续haystack: a b a b a ... needle: a b a b c ✓ ✓这里最关键的一点是haystack不需要回退我们只需要知道needle应该退到哪里才能继续利用前面已经匹配成功的信息。为了提前知道“失败以后应该退到哪里”KMP 会根据needle构造一个lps数组。lps是什么LPS全称是Longest Proper Prefix which is also Suffix先解释一下这里的前缀和后缀。对于一个字符串Prefix前缀从字符串最左边开始截取的一段内容。Suffix后缀从字符串最右边开始截取的一段内容。例如字符串abab的前缀有a、ab、aba后缀有b、ab、bab。其中最长的相同前缀和后缀是ab长度为2。这里的Proper Prefix / Proper Suffix表示不能把整个字符串自己算进去否则任何字符串都可以直接拿自己和自己比较就没有意义了。所以lps[i]表示对于needle[0:i1]这一段字符串它最长的相同前缀和后缀有多长。例如needle ababc 下标 0 1 2 3 4 字符 a b a b c lps 0 0 1 2 0当i 2时当前这一段是aba它最长的相同前后缀是a前缀a 后缀a所以lps[2] 1当i 3时当前这一段是abab最长的相同前后缀是ab前缀ab 后缀ab所以lps[3] 2这个2就是在告诉我们如果已经成功匹配abab但下一个字符失败那么前面还有长度为2的ab可以继续复用不需要完全从头开始。先构造 lps直接看构造代码会比较绕所以先看我们到底在做什么。假设前一个位置已经算出了lps[i - 1] length这意味着到i - 1为止已经存在长度为length的相同前缀和后缀。现在加入新的needle[i]我们首先会想原来这组相同前后缀能不能再往后延长一个字符这就是为什么要去比较needle[i]needle[length]这里的needle[i]是当前新加入的字符而needle[length]是前缀中下一个等待匹配的字符。例如当前已经有abab 最长相同前后缀ab length 2如果再加入a变成ababa原来的ab想继续延长就需要比较当前新字符needle[4] a 前缀下一个字符needle[2] a两者相同所以原来的ab ab可以延长成aba aba因此length1lps[i]length此时lps[4] 3。所以第一种情况就是ifneedle[i]needle[length]:length1lps[i]length i1意思就是当前字符能够接在已有的相同前后缀后面所以相同前后缀长度增加 1。如果不相同为什么不能直接把length变成 0这里的“不相同”具体指的是needle[i]!needle[length]那这两个位置为什么要比较因为此时我们已经知道前面存在一组长度为length的相同前缀和后缀现在想看看它们能不能再同时延长一个字符。举个例子needle aabaaab假设现在准备计算i 5这一位也就是当前这一段a a b a a a 0 1 2 3 4 5 ↑ i在加入第5个字符之前我们已经算出了aabaa它最长的相同前缀和后缀是前缀aa 后缀aa所以length 2可以把当前状态看成a a b a a ^^^^ 前缀 aa ^^^^ 后缀 aa现在又来了一个新的字符needle[5] a我们首先想原来的aa aa能不能继续延长成长度 3如果想让长度从2变成3前缀这一边接下来应该是什么字符原来的前缀已经用了needle[0:2] aa所以下一个字符就是needle[length]也就是needle[2] b而后缀这一边新加入的字符就是needle[i] needle[5] a于是我们比较needle[i] a needle[length] b发现a ! b这就是代码里的needle[i]!needle[length]它表达的不是“整个字符串失败了”而只是原来长度为 2 的aa这组前后缀不能继续延长成长度 3。因为如果能延长本来应该得到前缀aab 后缀aaa但aab ! aaa所以长度3这条路失败了。但为什么不能直接length0因为长度 2 的方案失败不代表长度 1 的方案也失败。我们原来用的是aa而aa自己还有一个更短的相同前缀和后缀a也就是说可以退一步不再尝试长度 2aa而改成尝试长度 1a这个“更短的可用长度”之前其实已经算过了lps[1] 1所以代码写成lengthlps[length-1]原来length 2变成length lps[1] 1这时候i不动仍然是i 5 needle[i] a只是换成长度为1的方案重新试。现在比较needle[i] needle[5] a needle[length] needle[1] a这次a a成功了。所以原来的长度1可以继续延长length 1 1 2最终lps[5] 2再看当前字符串aabaaa它确实有前缀aa 后缀aa所以答案正好是lps[5] 2因此, 流程就是原来已经有 length 2 → 前后缀都是 aa 想继续延长 → 比较 needle[i] 和 needle[length] a ! b → 长度 2 的方案无法继续延长 但不是直接清零 → 因为 aa 自己还有更短的可用前后缀 a length lps[length - 1] → length 从 2 退到 1 还是拿同一个 needle[i] a 再试 a a → 长度 1 的方案可以延长 最终 length 2 → lps[i] 2所以, 写代码为eliflength0:lengthlps[length-1]当前最长的前后缀没办法继续延长那就退到下一个更短、已经被证明有效的前后缀再拿当前字符重新尝试。而i为什么不增加也就很好理解了因为我们还没有算完lps[i]只是换了一个候选长度当前这个字符还得继续试。如果已经退到length 0还是不相同呢这时候说明已经没有任何更短的前后缀可以继续尝试了因此lps[i]0i1也就是当前这一段不存在相同的非空前缀和后缀当前答案就是0然后继续计算下一格。所以整个构造过程其实只有三个问题1. 当前最长前后缀还能继续延长吗 能 → length 1 → lps[i] length → i 1 2. 不能延长但还有更短的前后缀可以尝试吗 有 → length lps[length - 1] → i 不动 → 用当前字符重新尝试 3. 已经没有任何前后缀可以尝试了吗 是 → lps[i] 0 → i 1对应代码就是lps[0]*len(needle)length0i1whileilen(needle):ifneedle[i]needle[length]:length1lps[i]length i1eliflength0:lengthlps[length-1]else:lps[i]0i1这里两个变量的职责就是i当前正在计算哪一个lps[i]length当前正在尝试的相同前后缀长度同时也是前缀中下一个需要比较的位置再使用lps进行匹配lps构造完成以后就可以真正开始比较haystack和needle。i0j0whileilen(haystack):ifhaystack[i]needle[j]:i1j1ifjlen(needle):returni-jelse:ifj0:jlps[j-1]else:i1这里i当前检查haystack的哪个字符j当前检查needle的哪个字符如果haystack[i]needle[j]说明当前字符匹配成功两个指针一起向后移动i1j1如果jlen(needle)说明整个needle已经匹配完成。此时i已经走到了匹配内容的后一个位置而j正好等于needle的长度所以起点就是i-j如果字符不同则分两种情况。如果j0说明连needle的第一个字符都没有匹配成功前面没有任何信息可以继续利用所以只能i1继续检查haystack的下一个字符。如果j0说明前面已经有一部分字符匹配成功这时候haystack的i不需要回退只调整jlps[j-1]意思就是根据刚才已经匹配成功的那一段找到一个更短但仍然可以复用的前后缀然后继续拿当前的haystack[i]比较。所以 KMP 和暴力方法最大的区别就是暴力匹配失败 → 换一个起点 → needle 从头重新比较 → 前面已经匹配成功的信息基本全部丢掉而 KMP 是匹配失败 → haystack 不回退 → 根据 lps 调整 needle 的位置 → 继续复用前面已经匹配成功的信息完整代码classSolution:defstrStr(self,haystack:str,needle:str)-int:# 1. 构造 lpslps[0]*len(needle)length0i1whileilen(needle):ifneedle[i]needle[length]:length1lps[i]length i1eliflength0:lengthlps[length-1]else:lps[i]0i1# 2. KMP 匹配i0j0whileilen(haystack):ifhaystack[i]needle[j]:i1j1ifjlen(needle):returni-jelse:ifj0:jlps[j-1]else:i1return-1所以 KMP 最值得记住的并不是lps的代码而是两个“复用”构造lps时如果最长前后缀失败就利用之前算好的lps去寻找更短的前后缀真正匹配时如果needle匹配失败又利用lps决定j应该退到哪里。也就是说KMP 从头到尾都在做同一件事已经算过的信息不要轻易丢掉能复用就继续复用。 如果只是 Python 实际开发不要求手写匹配算法也可以直接使用haystack.find(needle)它本身就会返回第一次出现的位置找不到则返回-1。但在算法题里自己实现这一遍的意义主要还是理解枚举起点 → 逐字符验证 → 失败后换起点 → 成功后返回第一个匹配位置以及进一步思考暴力算法中有哪些已经计算过的信息被重复丢弃了而这些信息能不能被下一轮复用。