LeetCode 28 找出字符串中第一个匹配项的下标

1. 题目28. 找出字符串中第一个匹配项的下标 - 力扣LeetCode题目描述给你两个字符串haystack和needle在haystack字符串中找出needle字符串出现的第一个位置下标从 0 开始。如果不存在则返回-1。示例输入haystack sadbutsad, needle sad输出0输入haystack leetcode, needle leeto输出-1约束(1 haystack.length, needle.length 10^4)haystack和needle仅由小写英文字符组成2. 最佳解题思路描述暴力双指针朴素匹配适合入门遍历主串每个下标i当haystack[i] needle[0]时开启子串匹配从 i 开始连续比对 len(needle) 个字符全部匹配成功直接返回起始下标i中途字符不相等匹配失败重置标记继续外层循环遍历结束无匹配返回-1。优势逻辑直白容易手写无需复杂 KMP 预处理适合题目数据范围。时间复杂度最坏 (O(n*m))空间 (O(1))。3. 我的可优化代码逻辑大体正确存在边界 bug 与冗余变量class Solution { public: int strStr(string haystack, string needle) { int len needle.size(); int num 0; int index -1; int flag 0; for(int i 0;ihaystack.size();i){ if(haystack[i]needle[0]){ index i; for(int j i;jilen;j){ if(haystack[j] needle[j-i]){ ​ } else{ index -1; break; } } } if(index!-1){ break; } } return index; } };代码问题说明数组越界风险致命 bug内层循环j i len没有限制j haystack.size()。若主串剩余字符不足len个haystack[j]访问越界程序崩溃。例haystackabc, needlebcdi1 时 ilen4j 取到 3 超出下标。无效冗余变量num、flag定义后全程未使用无意义可直接删除。空循环体可读性差相等时无操作仅不相等才处理逻辑阅读困难。循环范围可剪枝优化外层i最多只需走到haystack.size() - len超过该起点不可能完整容纳子串减少无效循环。4. 规范修正版代码朴素暴力匹配修复越界class Solution { public: int strStr(string haystack, string needle) { int n haystack.size(); int m needle.size(); // 剪枝i最大到 n-m再往后长度不够 for (int i 0; i n - m; i) { bool match true; for (int j 0; j m; j) { if (haystack[i j] ! needle[j]) { match false; break; } } if (match) { return i; } } return -1; } };5. 总结原代码核心匹配逻辑思路没问题但缺少长度边界判断存在数组越界崩溃优化关键点外层循环上限设为n-m从根源避免内层越界无需多余标记变量用 bool 记录单次匹配状态更清晰找到匹配起点直接 return不用额外保存 index 再 break。6. 相关知识拓展拓展 1库函数极简写法面试仅作了解int strStr(string haystack, string needle) { size_t pos haystack.find(needle); return pos string::npos ? -1 : pos; }底层封装匹配逻辑面试不建议作为主力解法。拓展 2KMP 算法高效线性匹配大数据最优预处理 needle 得到 next 前缀数组匹配失败时主串指针不回退时间 (O(nm))class Solution { public: int strStr(string haystack, string needle) { int n haystack.size(), m needle.size(); if(m 0) return 0; vectorint next(m,0); // 构建next数组 for(int i1,j0;im;i){ while(j0 needle[i]!needle[j]) jnext[j-1]; if(needle[i]needle[j]) j; next[i]j; } // 匹配 for(int i0,j0;in;i){ while(j0 haystack[i]!needle[j]) jnext[j-1]; if(haystack[i]needle[j]) j; if(jm) return i-m1; } return -1; } };拓展 3复杂度对比朴素暴力修正版最坏 (O(n*m))(O(1))KMP 算法(O(nm))(O(m))string::find底层优化实现实际效率很高。拓展 4易错点复盘忘记限制外层 i 上限导致内层访问主串越界多余无用变量增加代码冗余内层循环判断只处理不相等分支可读性差。