LeetCode日记–28.Implement strStr()

发布于 2020-09-20  130 次阅读


碎碎念:今天周末,但是新生典礼在广场试音响,可吵死我了,又是没有肥宅快乐觉的一天。


本文于2020/9/21更新了关于KMP的讲解。以及我自己的KMP解法


题目如下:

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

本人思路:

其实就是暴力破解的优化版本,在优化版本的暴力破解中,只有模式串首尾和主串当前遍历到的首尾相同才试图进行匹配,同时若是匹配中出现了不一样的字符则立即break。

代码如下:

class Solution {
    public int strStr(String haystack, String needle) {
        int cur=0,leftPointer=0,rightPointer=needle.length() -1;
        int res = -1,flag = 0;
        if(needle.length()==0)
            return 0;
        while(cur<=(haystack.length()-needle.length())){
            leftPointer = cur;
            rightPointer = leftPointer + needle.length() - 1;
            if((haystack.charAt(leftPointer)==needle.charAt(0))&&(haystack.charAt(rightPointer)==needle.charAt(needle.length()-1))){
                for(int i=0;i<=(needle.length() -1);i++){
                    if(haystack.charAt(i+leftPointer)==needle.charAt(i))
                        flag = 1;
                    else{
                        flag = 0;
                        break;
                    }
                }
                if(flag==1){
                    res = cur;
                    return res;
                }

            }
            cur++;
        }
        return res;
    }
}

代码依旧又臭又长,不过第一次把所有case考虑到了,泪目.jpg。这个解法应该是稍微优于官方题解中的方法2的。

大佬思路:

官方题解中还有一种骚方法(方法三),似乎达到了常数级的时间复杂度。恕我愚笨,暂时没看懂,等到看懂了会回来补充说明。

至于这个模式匹配,我们怎么能不想到我们的快乐KMP呢!

这里有LeetCode上面一个非常不错的讲KMP算法的帖子。

上面那篇帖子的next数组也就图一乐,真讲得清楚还得看这篇。

其实关于KMP我们主要是要记住遍历的时候文本串不会走回头路,前缀表则是对比了首尾有多少重复的字符以后,决定该回溯多少位的文本串。

关于next数组的使用:

next数组中存的值,next[j+1]=k,则表示前面的j个字符(包括j)中,有k个前后缀相同。比方说上图中的“D”处,next数组的值为2,就说明“D”前面的“ABCDAB”中有两位的前后缀相同。

若在“D”处发生了失配,则指向模式串的指针应该指向p[2]处,因为数组从0开始,2正好是两位相同前缀后的下一位,即除了失配位,其他部分依然是匹配的。

关于next数组的获得:

当我们已知next[0,1....,j]的时候,我们要如何获得next[j+1]呢?

这时候就要分成两种情况讨论:

若p[k] == p[j],则next[j + 1 ] = next [j] + 1 = k + 1;
若p[k ] ≠ p[j],如果此时p[ next[k] ] == p[j ],则next[ j + 1 ] = next[k] + 1,否则继续递归前缀索引k = next[k],而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等,那么是否可能存在另一个值t+1 < k+1,使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢?如果存在,那么这个t+1 便是next[ j+1]的值,此相当于利用已经求得的next 数组(next [0, …, k, …, j])进行P串前缀跟P串后缀的匹配。

其中p[k]==p[j]的情况是挺简单的,就是直接next继续增大,k和j继续往后移动就是了。但是为什么p[k]!=p[j]的时候要递归查找p[next[k]]是否和p[j]相等呢?这时候我们来看一下上面这个图。本来呢,我们是在找长度为k的前后缀是否相等,但是现在已经确定不等了。但是我们又知道上图中前面k个长度是equal的(也就是说从k和j尾端数起的字符都是equal的),同时根据对称关系,k前面的某一段,和next[k]前面的某一段是equal的。那么我们就知道,next[k]前面的某一段和j前面的某一段是equal的,那么如果p[j]==p[next[j]]的话我们就有长度为 next[j]+1 的前后缀是equal的,若没有则继续递归查找next[next[j]]处,知道找到更短的前后缀可以匹配的地方(或者最终没找到)。

代码如下:

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0)
            return 0;
        if(haystack.length()==0||needle.length()==0)
            return -1;
        int[] next = getNext(needle);
        int k =0,j=0;//k和j分别用来遍历haystack和needle
        while(k<haystack.length()){
            if(j==needle.length()-1 && haystack.charAt(k)==needle.charAt(j)){
                return k - j;
            }
            if(haystack.charAt(k)==needle.charAt(j)){
                k++;
                j++;
            } else{
                j = next[j];
                if(j==-1){
                    j++;
                    k++;
                }
            }
        }
        return -1;
    }
    public int[] getNext(String needle){
            int[] next = new int[needle.length()];
            next[0] = -1;
            int len =-1,i=0;//i是用来遍历的后缀,len是前缀
            while( i < needle.length()-1){
                if(len == -1||needle.charAt(len)==needle.charAt(i)){
                    len++;
                    i++;
                    next[i]=len;
                }
                else{
//这里在回溯,一直回溯到找到或者是len==-1 即回到最开始的地方为止。
                    len = next[len];
                }
            }
            return next;
    }
}

不知道为啥KMP反而时间开销比暴力破解法大了很多,大概是因为测试的case不够长吧。


你好哇!欢迎来到雷公马碎碎念的地方:)