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

给你两个字符串 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 <= 104
haystack 和 needle 仅由小写英文字符组成

在我的回答中使用了kmp算法，可以极大的节省所用时间

class Solution {
public:int strStr(string haystack, string needle) {if (needle.empty()) return 0; // needle 为空，返回0// 构建部分匹配表vector<int> lps = computeLPS(needle);int i = 0, j = 0;while (i < haystack.size()) {if (haystack[i] == needle[j]) {++i;++j;}if (j == needle.size()) {return i - j; // 找到了完整匹配，返回起始位置} else if (i < haystack.size() && haystack[i] != needle[j]) {if (j != 0) {j = lps[j - 1];} else {++i;}}}return -1; // 没有找到匹配}private:vector<int> computeLPS(string needle) {int n = needle.size();vector<int> lps(n, 0);int len = 0; // 当前匹配的前缀的长度int i = 1;while (i < n) {if (needle[i] == needle[len]) {++len;lps[i] = len;++i;} else {if (len != 0) {len = lps[len - 1];} else {lps[i] = 0;++i;}}}return lps;}
};

strStr 方法：
- 先处理特殊情况，如果 needle 为空，则直接返回 0。
- 调用 computeLPS 方法计算 needle 的部分匹配表。
- 使用双指针 i 和 j 在 haystack 上进行匹配：
  - 如果当前字符匹配，则同时向后移动 i 和 j。
  - 如果 j 移动到 needle 的末尾，返回匹配起始位置 i - j。
  - 如果当前字符不匹配，并且 j 不为 0，则根据部分匹配表调整 j。
  - 如果 j 为 0，则移动 i 继续尝试匹配。
- 如果循环结束仍未找到匹配，则返回 -1。
computeLPS 方法：
- 构建 needle 的部分匹配表 lps。
- 使用 len 记录当前匹配的前缀的长度，i 表示当前字符。
- 根据当前字符与前缀的匹配情况更新 len 和 lps[i]。
- 如果不匹配，根据 len 调整 len 的值。

总结

通过使用 KMP 算法，可以高效地在 haystack 中查找 needle 的第一个匹配项的位置，时间复杂度为 O(m + n)，其中 m 是 haystack 的长度，n 是 needle 的长度。这种方法利用部分匹配表，在匹配过程中避免了回溯，使得算法效率得到了显著提升。

但是对于不熟悉kmp算法的人下面的一种方法更加简单

#include <string>using namespace std;class Solution {
public:int strStr(string haystack, string needle) {int hLen = haystack.length(); // 获取 haystack 的长度int nLen = needle.length();   // 获取 needle 的长度// 遍历 haystack，确保剩余长度足够容纳整个 needlefor (int i = 0; i <= hLen - nLen; ++i) {int j = 0;// 逐个字符比较 needle 和 haystack 中的对应位置for (j = 0; j < nLen; ++j) {if (needle[j] != haystack[i + j]) // 不匹配时退出内循环break;}if (j == nLen) // 如果 j 等于 needle 的长度，说明找到匹配return i; // 返回匹配起始位置}return -1; // 遍历完整个 haystack 后仍未找到匹配，返回 -1}
};

方法较为简单，但运行时间较长

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

总结

最新新闻

热搜词