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/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年11月18日
下一篇 2019年11月22日

相关推荐

  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • 剑指offer51-数组中的逆序对

    原题(来源Leetcode) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7…

    算法 2020年4月24日
    0390
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    090
  • leetcode557-反转字符串中的单词III

    原题 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1: 输入: “Let’s take LeetCode contest” 输出: …

    算法 2019年11月23日
    0120
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04570
  • leetcode820-单词的压缩编码

    原题 给定一个单词列表,我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。 例如,如果这个列表是 ["time", "me", "bell"],我们就可以将其表示为 S …

    算法 2020年3月28日
    090
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0110
  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0170
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01540
  • leetcode32-最长有效括号

    原题 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2…

    算法 2020年6月12日
    0160

发表回复

登录后才能评论