枚举
解题思路
枚举原串 str 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串 pattern 的「首位」开始尝试匹配：
- 匹配成功：返回本次匹配的原串 str 的「发起点」；
- 匹配失败：枚举原串 str 的下一个「发起点」，重新尝试匹配；
也就是说，对于「朴素匹配」而言，一旦匹配失败，将会将原串指针调整至下一个「发起点」，匹配串的指针调整至起始位置，然后重新尝试匹配；
复杂度
-
时间复杂度：
O(mn)，n 为原串的长度，m 为匹配串的长度； -
空间复杂度：
O(1)；
实现代码
var strStr = function (haystack, pattern) {
let haystackArr = [...haystack],
patternArr = [...pattern];
let haystackLen = haystack.length,
patternLen = pattern.length;
// 从原串的初始位置开始对比
for (let i = 0; i <= haystackLen - patternLen; i++) {
// 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
let hInx = i;
let pInx = 0;
// 一位一位对比匹配串
while (pInx < patternLen && haystackArr[hInx] == patternArr[pInx]) {
hInx++;
pInx++;
}
// 如果匹配索引 pInx 等于匹配串 patternLen 长度，说明，匹配串匹配原串成功
if (pInx == patternLen) return i;
}
return -1;
}
KMP 算法
解题思路
前置知识 KMP 算法；
KMP 算法 流程：
- 如果
原串[i] !== 匹配串[j]，匹配串[j] 匹配失败，则将 j 指针指向迁移位置的 next 数组所对应的值，即j = next[j - 1]；- 如果
原串[i] === 匹配串[j]，则继续向下匹配，匹配长度++；- 匹配长度 === 匹配串长度，则匹配成功；
复杂度
-
时间复杂度：
O(m+n)，n 为原串的长度，m 为匹配串的长度； -
空间复杂度：
O(m)，构建了 next 数组；
实现代码
var strStr = function (haystack, needle) {
if (needle.length === 0) return 0;
// 1. 构建 next 数组
let next = getNext(needle);
// 2. KMP 算法
for (let i = 0, j = 0; i < haystack.length; ++i) {
// 2-1. 如果 原串[i] !== 匹配串[j]，匹配串[j] 匹配失败，则将 j 指针指向迁移位置的 next 数组所对应的值，即 j = next[j - 1]
while (j > 0 && haystack[i] !== needle[j]) {
j = next[j - 1];
}
// 2-2. 如果 原串[i] === 匹配串[j]，则继续向下匹配，匹配长度++
if (haystack[i] === needle[j]) {
j++;
}
// 2.3. 匹配长度 === 匹配串长度，则匹配成功
if (j === needle.length) {
return i - needle.length + 1;
}
}
return -1;
};
const getNext = (needle) => {
const next = [0];
let j = 0;
for (let i = 1; i < needle.length; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
return next;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 218. 天际线问题
上一篇
评论
