LeetCode Top Interview Questions 28. Implement strStr() (Java版； Easy)

welcome to my blog

LeetCode Top Interview Questions 28. Implement strStr() (Java版; Easy)

题目描述

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().

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        char[] chs = haystack.toCharArray();
        char[] chs2 = needle.toCharArray();
        for(int i=0; i<chs.length; i++){
            int j=0;
            for(; j<chs2.length; j++){
                if(i+j>=chs.length || chs[i+j]!=chs2[j]){
                    break;
                }
            }
            if(j==chs2.length){
                return i;
            }
        }
        return -1;
    }
}

第一次做; KMP算法: 理解往前跳, 这样做的目的可以利用之前匹配过程的信息, 不用在匹配失败时从头开始匹配; 时间复杂度O(N)

/*
尝试KMP算法, KMP的时间复杂度是O(N)
*/
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.equals(""))
            return 0;
        if (haystack == null || haystack.isEmpty())
            return -1;
        //
        return kmp(haystack, needle);
    }

    public int kmp(String s, String m) {
        if (s == null || m == null || s.length() == 0 || s.length() < m.length())
            return -1;
        //
        char[] chs1 = s.toCharArray();
        char[] chs2 = m.toCharArray();
        int[] next = getNextArr(chs2);
        //chs1的索引
        int i1 = 0;
        //chs的索引
        int i2 = 0;
        //匹配流程
        /*
        在while循环中讨论3种情况(和getNextArr()中的三种情况相同, 区别在于每种情况的处理逻辑):
            1) 能匹配
            2) 不能匹配,但能往前跳
            3) 不能匹配,也不能往前跳
        */
        while (i1 < chs1.length && i2 < chs2.length) {
            //能匹配
            if (chs1[i1] == chs2[i2]) {
                i1++;
                i2++;
            }
            //不能匹配, 但是i2能往前跳
            else if (i2 > 0) {
                i2 = next[i2];
            }
            //不能匹配, i2也不能往前跳(也说明此时i2==0)
            else {
                i1++;
            }
        }
        //here,i1越界或者i2越界; 判断i2是否越界, i2越界的话说明匹配成功,返回匹配的第一个位置的索引; i2没越界的话,说明i1越界了, 匹配失败,返回-1
        //chs1: aleetc
        //chs2:  lee
        return i2 == chs2.length ? i1 - chs2.length : -1;


    }

    public int[] getNextArr(char[] chs) {
        if (chs.length == 1)
            return new int[]{-1};
        //next[i]表示[0,i-1]范围上前缀和后缀的最长匹配长度; 其中:前缀不包括最后一个字符,也就是chs[i]; 后缀不包括第一个字符,也就是chs[0]; 细节:都是从0开始匹配
        int[] next = new int[chs.length];
        //人为规定的初始化
        next[0] = -1;
        next[1] = 0;
        //跳到的对比的位置
        int cn = 0;
        int i = 2;
        /*
        在while循环中讨论3种情况:
            1) 能匹配
            2) 不能匹配,但能往前跳
            3) 不能匹配,也不能往前跳
        */
        while (i < next.length) {
            //能匹配
            if (chs[i - 1] == chs[cn]) {
                next[i++] = ++cn;
            }
            //不能匹配,但能往前跳
            else if (cn > 0) {
                //最核心
                cn = next[cn];
            }
            //不能匹配,也不能往前跳
            else {
                next[i++] = 0;
            }
        }
        return next;

    }
}

第一次做; 暴力匹配; 以不同的字符开始, 看看能不能匹配, 时间复杂度O(MN), 其实很快

/*
暴力匹配尝试的时间复杂度为O(MN)
可以用KMP算法
*/
class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.equals(""))
            return 0;
        if(haystack==null || haystack.isEmpty())
            return -1;
        //
        int n = haystack.length(), m = needle.length();
        for(int i=0; i<n-m+1; i++){
            if(match(haystack,needle,i))
                return i;
        }
        return -1;
    }
    public boolean match(String s1, String s2, int index){
        for(int i=0; i<s2.length(); i++){
            if(s1.charAt(index++) != s2.charAt(i))
                return false;
        }
        return true;
    }
}