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日

相关推荐

  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0130
  • leetcode128-最长连续序列

    原题 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长…

    算法 2020年6月6日
    090
  • leetcode61-旋转链表

    原题 给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。 示例1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->…

    算法 2019年12月17日
    0110
  • leetcode96-不同的二叉搜索树

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: &…

    算法 2020年1月22日
    0120
  • leetcode101-对称二叉树

    原题 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。     1  &nbsp…

    算法 2020年1月11日
    0120
  • leetcode236-二叉树的最近公共祖先

    原题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 …

    2020年1月15日
    080
  • leetcode35-搜索插入位置

    原题 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: […

    算法 2020年3月2日
    0120
  • leetcode454-四数相加II

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

    算法 2019年12月27日
    080
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0140
  • 剑指offer45-把数组排成最小的数

    原题(来源Leetcode) 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" …

    算法 2020年6月11日
    0140

发表回复

登录后才能评论