leetcode28-实现strStr()

原题

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:

needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

解法

JDK API

在leetcode上,当然可以投机取巧地使用String.indexof()方法,不用重复造轮子:

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

但这是一个经典的字符串精准模式匹配问题,历史上出现过很多解决这个问题的算法,掌握它们的思想还是有必要的:

BF算法(朴素算法)

思想

这是最直观、最简单的算法。从主串的第start个字符起和模式的第1个字符比较,如果相等继续逐个比较后续字符。比较过程中一旦发现不相等的情况,则回溯至主串中的第start+1个字符位置处,重新与模式P的字符进行比较。该算法效率较低。

代码

class Solution {
    public int strStr(String haystack, String needle) {
        int mainLen = haystack.length();
        int subLen = needle.length();
        if(needle.equals("")) return 0;//注意模式字符串为空的情况
        for(int i=0;i<mainLen;i++){
            for(int j =0;j<subLen;j++){
                if(!(i+j<mainLen)) return -1;//主串下标超出
                if(!(haystack.charAt(i+j)==needle.charAt(j))) break;
                else if(j == subLen-1) return i;//完全匹配,返回主串下标
            }
        }
        return -1;
    }
}

算法的复杂度为O[(i-j)j]

MP算法

思路

指针不回溯,利用已得到的“部分匹配”结果,将模式向右“滑动”若干位置后继续比较。

参考下面给出的示例:
haystack :"cdnidnidsm"
needle:"nidsm"
按照BF算法的思想,在比较haystack[2]needle[0]时,两个字符相等,然而比较到haystack[5]needle[3]的时候两个字符不等,于是回溯继续向后比较haystack[3]needle[0]。可是既然能确定haystack[2]-haystack[4]needle[0]-needle[2]是完全对应的。那么比较haystack[3]needle[0]实际上相当于比较needle[1]needle[0]。并且我们知道needle中前三个字符都是不同的。所以只需要从haystack[5]处继续跟needle[0]比较就行了。并且needle中字符的这些关系完全是一开始就可以确定的。

我们称记录模式字符串中各个字符之间关系的函数为失效函数
失效函数的定义域是模式字符串在“失配”前匹配的字符串个数。取值j属于0~Len(P)-1

获取失效函数的方法:

失效函数的取值k满足P0P1…Pk = Pj-kPj-k+1…Pj。如果不存在这个k值,取-1。

直观的看k就是模式字符串前j个字符是否存在前k+1位等于后k+1位。

nidsm的失效函数为:

j 0 1 2 3 4
p(j) n i d s m
k -1 -1 -1 -1 -1

再举一个例子,caatcat的失效函数为:

j 0 1 2 3 4 5 6
p(j) c a a t c a t
k -1 -1 -1 -1 0 1 -1

得到了失效函数后,即可使用MP算法进行匹配。假设在某一轮比较中,失配的情况发生在模式P的第j位,如果j=0,进行下一轮比较时,目标指针向后移动一位,模式的起始比较地址回到P0,其他情况进行下一轮比较时,目标指针不发生回溯,而模式P的起始比较地址为j-1对应的失效函数的值+1

当然也可以把这个值提前算出来便成为了Next()函数:

j 0 1 2 3 4 5 6 7
p(j) c a a t c a t
Next(j) -1 0 0 0 0 1 2 0

Next(7)可以用于继续匹配(可能要求找出所有匹配的子字符串)。

代码

class Solution {
    //获取next函数
    public int[] next(String needle){
        int len = needle.length();
        int i = 0;
        int j = -1;
        int[] next = new int[len+1];
        next[0] = -1;
        while(i < len){
            while( j > -1 && needle.charAt(i)!=needle.charAt(j))
                j = next[j];//j会有一个传递的效果,必须前一个i对应的j是1,下一个i对应的j才能是2。如果遇到不同的字符则j清零
            next[++i] = ++j;
        }
        return next;
    }
    public int strStr(String haystack, String needle) {
        int mainLen = haystack.length();
        int subLen = needle.length();
        if(needle.equals("")) return 0;//注意模式字符串为空的情况
        if(mainLen<subLen) return -1;
        int[] next = next(needle);
        int i = 0;
        int j = 0;

        while(j < mainLen){
            while(i>-1 && needle.charAt(i) != haystack.charAt(j))
                i = next[i];
            i++;
            j++;
            if(i >= subLen){
                return j-i;
            }
        }
        return -1;
    }
}

KMP算法

思路

在MP算法的基础上,还要避免最长前缀之后的那个字符不等于原来失配的那个字符。
下面在已知mpNext表的情况下,给出建立kmpNext表的规则。这个规则分为四种情况:

  1. 如果mpNext[j] = 0且Pj = P0,则令kmpNext[j] = -1。
  2. 如果mpNext[j] = 0且Pj ≠ P0,则令kmpNext[j] = 0。
  3. 如果mpNext[j] ≠ 0且Pj ≠ PmpNext[j],则令kmpNext[j] = mpNext[j]。
  4. 如果mpNext[j] ≠ 0且Pj = PmpNext[j],则用mpNext[j]的值替换原来mpNext[j]中的j值,直到情况转换为前3种情况的一种,进而递归地求解kmpNext[j]。
j 0 1 2 3 4 5 6 7
p(j) c a a t c a t
mpNext(j) -1 0 0 0 0 1 2 0
kmpNext(j) -1 0 0 0 -1 0 2 0

代码

class Solution {
    //获取kmpNext数组
    public int[] next(String needle){
        int len = needle.length();
        int i = 0;
        int j = -1;
        int[] next = new int[len+1];
        next[0] = -1;
        while(i < len-1){
            while( j > -1 && needle.charAt(i)!=needle.charAt(j))
                j = next[j];
            i++;
            j++;
            if(needle.charAt(i) == needle.charAt(j))
                next[i] = next[j];
            else
                next[i] = j;
        }
        return next;
    }

    public int strStr(String haystack, String needle) {
        int mainLen = haystack.length();
        int subLen = needle.length();
        if(needle.equals("")) return 0;//注意模式字符串为空的情况
        if(mainLen<subLen) return -1;
        int[] next = next(needle);
        int i = 0;
        int j = 0;

        while(j < mainLen){
            while(i>-1 && needle.charAt(i) != haystack.charAt(j))
                i = next[i];
            i++;
            j++;
            if(i >= subLen){
                return j-i;
            }
        }
        return -1;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode28-%e5%ae%9e%e7%8e%b0strstr/