代码随想录Day9-Leetcode28. 实现 strStr()，459.重复的子字符串

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查找,替换字符;
当然,滑动窗口和双指针的运用是共通的,只是处理的细节不同;

双指针回顾

在数组,链表, 字符串等相关问题中, 双指针在移动元素,查找元素等方面都有很大作用