[Leetcode] Implement strStr() 实现StrStr

remcarpediem 发布于2019-08-14 12:26 / 2359人阅读

摘要：最新更新暴力法复杂度时间空间思路本题有很多高级算法可以在时间内解决问题，然而这已经超出面试的范畴。本题在面试中出现的作用就是考察基本的编程素养，以及边界条件的考虑。它使用一个数组，这个数组记录了模式串自身的前缀和后缀的重复情况。

Implement strStr() 最新更新：https://yanjia.me/zh/2019/02/...

Implement strStr().

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

暴力法 复杂度

时间 O(N^2) 空间 O(1)

思路

本题有很多高级算法可以在O(N)时间内解决问题，然而这已经超出面试的范畴。本题在面试中出现的作用就是考察基本的编程素养，以及边界条件的考虑。我们用暴力法即可。

代码

public class Solution {
    public int strStr(String haystack, String needle) {
        int start = 0;
        // 如果剩下的字母不够needle长度就停止遍历
        while(start <= haystack.length() - needle.length()){
            int i1 = start, i2 = 0;
            while(i2 < needle.length() && haystack.charAt(i1)==needle.charAt(i2)){
                i1++;
                i2++;
            }
            if(i2 == needle.length()) return start;
            start++;
        }
        return -1;
    }
}

KMP算法 复杂度

时间 O(N+M) 空间 O(M)

思路

KMP算法是较为高级的算法。它使用一个next数组，这个数组记录了模式串needle自身的前缀和后缀的重复情况。同样是双指针进行匹配，当失配时可以根据这个数组找到应该将模式串向后位移多少位，避免一些重复的比较。具体的解法这里有两篇文章比较好，一篇是详细讲解KMP算法。

如果看完对产生next数组的方法还不太明白，还有一篇是讲解next数组怎么得到的。

代码

public class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0){
            return 0;
        }
        int[] next = new int[needle.length()];
        // 得到next数组
        getNextArr(next, needle);
        // i是匹配串haystack的指针，j是模式串needle的指针
        int i = 0, j = 0;
        // 双指针开始匹配
        while(i < haystack.length() && j < needle.length()){
            // 如果j=-1意味着刚刚失配过，下标+1后，下一轮就可以开始匹配各自的第一个了
            // 如果指向的字母相同，则下一轮匹配各自的下一个
            if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            // 如果失配，则将更新j为next[j]
            } else {
                j = next[j];
            }
        }
        return j == needle.length() ? i - j : -1;
    }
    
    private void getNextArr(int[] next, String needle){
        // k是前缀中相同部分的末尾，同时也是相同部分的长度，因为长度等于k-0。
        // j是后缀的末尾，即后缀相同部分的末尾 
        int k = -1, j = 0;
        next[0] = -1;
        while(j < needle.length() - 1){
            // 如果k=-1，说明刚刚失配了，则重新开始计算前缀和后缀相同的长度
            // 如果两个字符相等，则在上次前缀和后缀相同的长度加1就行了
            if (k == -1 || needle.charAt(j) == needle.charAt(k)){
                k++;
                j++;
                next[j] = k;
            } else {
            // 否则，前缀长度缩短为next[k]
                k = next[k];
            }
        }
    }
}

云服务器 GPU云服务器 strstr mb_strstr Implement LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64476.html

LeetCode 28：实现strStr() Implement strStr()

摘要：爱写作者爱写实现函数。说明当是空字符串时，我们应当返回什么值呢这是一个在面试中很好的问题。对于本题而言，当是空字符串时我们应当返回。这与语言的以及的定义相符。利用内建函数直接得结果。如果子字符串为空，返回。爱写bug（ID：icodebugs）作者：爱写bug 实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符...

alaege 2019-08-16 18:31 评论0 收藏0
LeetCode 28：实现strStr() Implement strStr()

摘要：爱写作者爱写实现函数。说明当是空字符串时，我们应当返回什么值呢这是一个在面试中很好的问题。对于本题而言，当是空字符串时我们应当返回。这与语言的以及的定义相符。利用内建函数直接得结果。如果子字符串为空，返回。爱写bug（ID：icodebugs）作者：爱写bug 实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符...

ivydom 2019-07-31 11:26 评论0 收藏0
leetcode 28 Implement strStr()

摘要：如果存在，返回子字符串的在长字符串的起始点的位置。如果不存在，则返回。就是遍历长字符串，并通过比较字符找到是否存在目标子字符串。需要注意一下的就是对特殊情况的判断，以减少无谓的时间消耗。题目详情 Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if nee...

Gemini 2019-08-15 14:16 评论0 收藏0
[LeetCode] Implement strStr()

Problem Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Note 有substring，为何不用。 Solution public class Solution { public ...

fuyi501 2019-08-14 14:03 评论0 收藏0
leetcode28 Implement strStr() 在字符串中寻找目标字符串

摘要：题目要求在子字符串中寻找目标字符串，并返回该字符串第一次出现时的下标在尝试的写了一提中等难度的题目后，又一次回到简单难度的题寻找温暖思路一在原字符串中中寻找目标字符串首字母的下标，并提取子字符串，若该字符串的开头等于目标字符串，则返回该下题目要求：在子字符串中寻找目标字符串，并返回该字符串第一次出现时的下标在尝试的写了一提中等难度的题目后，又一次回到简单难度的题寻找温暖T-T 思...

FingerLiu 2019-08-14 17:55 评论0 收藏0