28. 实现 strStr()
这题之前写过, 而且印象深刻的是细节很多,所以这边是看完以前的代码,再写的(几乎是在背代码了hhh)
甚至这样, next[0]=-1, 和j开始匹配子串是没初始化成0这样的细节还是忘了
手撕kmp感觉光靠理解是有困难的
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
//为了避免自我折磨, 我先看下代码总结下思路;
//对子串构建一个next数组, next[i]的值表示:若在i处失配, 则可以从next[i]处重新开始匹配;
//构建方法为:从i=0,j=-1开始模拟一次针对自身的匹配, 加上一句"next[i] = j"
//这其中有一些稍微复杂的数学概念, 即pmt,PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度
//例如abababca,pmt为[00123401],next为[-1,0,0,1,2,3,4,0]
//细节:next[0] = -1是为了方便i++,j++的写法;
//先++再next[i] = j也是因为在第i位失配(已经不相等了)后,返回的是已匹配子串的后一位
var strStr = function(haystack, needle) {
let next = new Array(needle.length).fill(0)
next[0] = -1
let i =0, j =-1;
while(i<needle.length){
if(j==-1||needle[i] == needle[j]){
i++
j++
next[i] = j
}else{
j = next[j]
}
}
i =0, j =0
while(i<haystack.length){
if(j==-1||haystack[i] == needle[j] ){
i++
j++
}else{
j = next[j]
}
if(j==needle.length){
return i-j
}
}
return -1
};
看了文章后发现, 我这里next的求法有点过于优雅, 虽然适合背,但细节不够了,不适合理解和改动
后面要求pmt的时候我就不知道怎么改了,有空二刷理解下文章里的求法
459. 重复的子字符串
开始时搞半天pmt, 结果发现没有关系,尬住了
/**
* @param {string} s
* @return {boolean}
*/
//背代码的坏处是, 题目变了一下就不会了
//可以求一下pmt,如果pmt[len-1]>=s.len/2的话,就成立,大概
//思路错了,那么pmt是递增的?
//pmt的求法是, ?
//绷不住了, 只会用求next的方法反推pmt了,太搞了
//这个实现太优雅和简便,导致我不知道它应有的细节
//草了, 跟pmt半毛钱关系没有
var repeatedSubstringPattern = function(s) {
return (s+s).indexOf(s,1)!=s.length
};
字符串总结
总体来说, 字符串的很多题可以用库函数解,但如果库函数是解题的核心,就还是别用了;
即使是在js中, 也应当转为数组处理;
尽管是以数组的形式处理,不过由于性质问题, 处理的很多问题跟数组是不一样的;
数组更多的是排序,给出值的关系并查找某个(些)数,
而字符串更多的是反转,kmp查找,替换字符;
当然,滑动窗口和双指针的运用是共通的,只是处理的细节不同;
双指针回顾
在数组,链表, 字符串等相关问题中, 双指针在移动元素,查找元素等方面都有很大作用