【JavaScript】Leetcode每日一题-实现strStr()
【题目描述】
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例1：
输入：haystack = "hello", needle = "ll"
输出：2
示例2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
示例3：
输入：haystack = "", needle = ""
输出：0
提示：
0 <= haystack.length, needle.length <= 5 * 10^4
haystack 和 needle 仅由小写英文字符组成
【分析】
暴力搜索：
顾名思义，直接暴力搜索匹配即可。
-
代码：
var strStr = function(haystack, needle) {
var nlen = needle.length;
var hlen = haystack.length;
for(var i=0;i <= hlen - nlen;i++){
if(haystack.slice(i, i+nlen) == needle){
return i;
}
}
return -1;
};
Sunday解法：
参考：Sunday题解
重点：
-
代码：
var strStr = function(haystack, needle) {
var hash = {};
var nlen = needle.length;
var hlen = haystack.length;
for(var i='a';i <= "z";){
hash[i] = nlen;
i = String.fromCharCode(i.charCodeAt() + 1);
}
for(var i in needle){
hash[needle[i]] = nlen - i;
}
var index = 0;
for(var i=0;i <= hlen - nlen;){
if(haystack.slice(i, i+nlen) == needle){
return i;
}
else{
i += hash[haystack[i+nlen]];
}
}
return -1;
};
KMP：
思路：
暴力过程中，原串i每次位移一位，且当不匹配时，i会回溯到匹配起始位置，而我们的KMP则是保证i不会回溯，在不匹配位置继续向前匹配，实现则需要一个对模式串预处理得到的next数组，数组表示
不匹配位置向前移动j(已进行匹配操作长度、当前模式串索引值)后回跳的位数，比如可以参见上图理解，例如，第5位不匹配，则可以直接向后位移5位，再回跳2位。
-
或者可以理解成，将next[j]位置移到不匹配位置，例如，当第5位匹配出错时，将第二位即b移到当前不匹配位置。
则此时两个a刚好匹配上，而i可以从不匹配位置继续向前走，匹配过程由于i不回溯，时间复杂度为\(O(n)\)。
next数组构建过程算是KMP精妙之处吧！
const next = new Array(m+1).fill(0); //默认第一位不用，方便计算
let i = 1, j = 0;
while (i < m) {
if (j == 0 || needle[i-1] == needle[j-1])
{++i; ++j; next[i] = j;}
else j = next[j]; //回调j直到j=0或needle[i]=needle[j]
} //对着示例想一遍就明白了
因此，时间复杂度为\(O(n+m)\)。
var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
if (m === 0) {
return 0;
}
const next = new Array(m+1).fill(0);
let i = 1, j = 0;
while (i < m) {
if (j == 0 || needle[i-1] == needle[j-1]){
++i; ++j; next[i] = j;
}
else{
j = next[j];
}
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = next[j + 1] - 1;
}
if (haystack[i] == needle[j]) {
j++;
}
if (j === m) {
return i - m + 1;
}
}
return -1;
};
KMP优化：
如图，next数组有时候效果并不理想，于是增添nextval数组记录最佳偏移。
var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
if (m === 0) {
return 0;
}
// const next = new Array(m+1).fill(0);
const nextval = new Array(m+1).fill(0);
let i = 1, j = 0;
while (i < m) {
if (j == 0 || needle[i-1] == needle[j-1])
{++i; ++j;
if(needle[i-1] != needle[j-1]){
nextval[i] = j;
}
else{
nextval[i] = nextval[j];
}
}
else j = nextval[j];
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = nextval[j + 1] == 0 ? 0 : nextval[j + 1] - 1;
}
if (haystack[i] == needle[j]) {
j++;
}
if (j === m) {
return i - m + 1;
}
}
return -1;
};
内置函数（离谱
var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
