题目概览给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串的第一个匹配项的下标下标从 0 开始。如果needle不是haystack的一部分则返回-1。示例 1输入haystack sadbutsad, needle sad 输出0 解释sad 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 所以返回 0 。示例 2输入haystack leetcode, needle leeto 输出-1 解释leeto 没有在 leetcode 中出现所以返回 -1 。提示1 haystack.length, needle.length 10^4haystack和needle仅由小写英文字符组成来源28. 找出字符串中第一个匹配项的下标 - 力扣LeetCode解题分析方法一暴力求解算法思路暴力匹配Brute Force是最直观的字符串匹配方法。从 haystack 的每个位置开始逐个字符与 needle 进行比较如果完全匹配则返回当前位置如果不匹配则从 haystack 的下一个位置重新开始比较。实现步骤遍历 haystack 的每个可能起始位置 i从 0 到 m-n对于每个起始位置 i比较 haystack[i...in-1] 与 needle[0...n-1] 的每个字符如果所有字符都匹配返回当前起始位置 i如果中途发现不匹配则从下一个起始位置 i1 重新开始比较如果遍历完所有可能起始位置都没有找到匹配返回 -1代码解析class Solution { public int strStr(String haystack, String needle) { int m haystack.length(), n needle.length(); int i 0, j 0; // 双指针遍历i 指向 haystackj 指向 needle while(i m j n) { if (haystack.charAt(i) needle.charAt(j)) { // 当前字符匹配 if (j n - 1) { // 如果 needle 的所有字符都已匹配返回起始位置 return i - j; } i; j; } else { // 当前字符不匹配回溯到下一个起始位置 i i - j 1; // i 回溯到下一个起始位置 j 0; // j 重置为 0重新开始匹配 } } return -1; // 遍历结束未找到匹配 } }时间复杂度O(m×n)其中 m 是 haystack 长度n 是 needle 长度。最坏情况下需要比较 m×n 次。空间复杂度O(1)只使用了常数级别的额外空间。优点实现简单易于理解不需要预处理。缺点效率较低当字符串较长时性能较差。方法二KMP算法思路KMPKnuth-Morris-Pratt算法通过预处理模式串needle构建 next 数组部分匹配表在匹配失败时利用已匹配的信息跳过不必要的比较避免回溯主串指针。核心概念前缀字符串的前缀是指从第一个字符开始但不包含最后一个字符的所有子串后缀字符串的后缀是指从最后一个字符结束但不包含第一个字符的所有子串最长公共前后缀长度对于模式串的每个位置计算该位置之前子串的最长相等前后缀的长度next 数组存储每个位置的最长公共前后缀长度用于匹配失败时确定模式串的移动位置实现步骤构建 next 数组预处理模式串计算每个位置的最长公共前后缀长度匹配过程使用双指针 i主串指针和 j模式串指针进行匹配如果字符匹配两个指针都向前移动如果字符不匹配且 j0根据 next 数组回退 j 指针如果字符不匹配且 j0只移动 i 指针当 j 等于模式串长度时匹配成功返回起始位置代码解析class Solution { public int strStr(String haystack, String needle) { int m haystack.length(), n needle.length(); if (n 0) return 0; // 空字符串直接返回 0 // 1. 构建 next 数组部分匹配表 int[] next new int[n]; int i 1, len 0; // len 记录当前最长公共前后缀长度 while(i n) { // 如果当前字符与 len 位置的字符匹配 while(i n needle.charAt(i) needle.charAt(len)) { len; next[i] len; // 记录当前位置的最长公共前后缀长度 i; } // 处理不匹配的情况 if (i n) { if (len 0) { // 回退到前一个最长公共前后缀的位置 len next[len - 1]; } else { // len 已经是 0当前位置的 next 值为 0 len 0; i; } } } // 2. 使用 next 数组进行匹配 i 0; // 主串指针 int j 0; // 模式串指针 while(i m j n) { // 字符匹配时两个指针都向前移动 while(i m j n haystack.charAt(i) needle.charAt(j)) { i; j; } // 如果模式串完全匹配返回起始位置 if (j n) { return i - n; } // 字符不匹配时的处理 if (j n) { if (j 0) { // 根据 next 数组回退模式串指针 i i - j next[j - 1] 1; // 主串指针移动到下一个可能匹配的位置 j next[j - 1]; // 模式串指针回退到最长公共前后缀的位置 } else { // 模式串第一个字符就不匹配只移动主串指针 i; } } } return -1; // 未找到匹配 } }时间复杂度O(mn)其中 m 是 haystack 长度n 是 needle 长度。构建 next 数组需要 O(n)匹配过程需要 O(m)。空间复杂度O(n)需要额外的 next 数组存储部分匹配信息。优点效率高避免了主串指针的回溯适合处理长字符串匹配。缺点实现相对复杂需要理解部分匹配表的概念。应用场景文本编辑器查找、IDE 代码搜索、生物信息学中的基因序列匹配等需要高效字符串匹配的场景。
