侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-28. 实现 strStr()

阿里灰太狼
2021-11-13 / 0 评论 / 0 点赞 / 152 阅读 / 1,752 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-11-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

cj46.pngcj47.png

JAVA解法

// 暴力解法
class Solution {
    public int strStr(String haystack, String needle) {
        // 获得两个传进来的字符串长度
        int n = haystack.length(), m = needle.length();
        // 对 haystack 进行遍历
        for (int i = 0; i + m <= n; i++) {
            // flag 标志
            boolean flag = true;
            // haystack 从头与 needle 进行比较
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            // 若存在则 flag 为 true,返回开始相同的索引
            if (flag) {
                return i;
            }
        }
        // 不存在则返回 -1
        return -1;
    }
}
// KMP 解法
class Solution {
    public int strStr(String haystack, String needle) {
        
        // 获取两个字符串的长度
        int n = haystack.length(), m = needle.length();

        // haystack 为空
        if (m == 0) {
            return 0;
        }

        // 构建一个存储优化所要移动的长度的数组
        int[] next = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        
        /**
            对 haystack 进行遍历,若 haystack.charAt(i) == needle.charAt(j)
              一直成立,则不会进入 while 并且 j++ 到 needle 的长度,匹配成功。
              若 haystack.charAt(i) != needle.charAt(j) 时,在 i 不变的的情
              况下则要查在 next[] 中上一个 haystack.charAt(i) == needle.charAt(j)
              的 j 的值当做当前的识别位置,这个过程为 needle 的识别指针在移动,移动到
              有相同前后缀的前缀最后一个位置。敲黑板了,重难点就是这,这也是
              KMP 算法的核心。
        */
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}

leetcode原题: 28. 实现 strStr()

解法分析

对于传进来的两个字符串,先获取它们的长度,然后对要分析的字符串 haystack 进行遍历,从 haystack 字符串的第0个开始部分字符串(长度为目标字符串的长度 needle.length)与目标字符串 needle 进行对比,用 flag 来记录是否找到目标字符串。

haystack 字符串的第0个字符开始的部分字符串中存在与 needle 不同的字符时,跳过循环,从 haystack 字符串的第1个字符开始,以此类推。

找到目标字符串 needle 后 flag 为 true,返回 haystack 当前的开始字符的索引并返回,若不存在则返回-1,暴力算法用时 1300ms 左右,而 KMP 算法则只要 5ms。虽然是简单题,难度不低,用上 KMP 应该归类中等或困难,很好的一道题,值得研究。

这道题的目的是实现类似 C 语言的 strstr() 以及 Java 的 indexOf() 定义符。可以直接调用 indexOf() 就能解出来而且只需 0ms,但是纯属卡 bug ,这道题的目的就是实现这个 indexOf() 方法的功能,要是面试这样作答,那面试到此结束,回去等通知吧。

我能理解 KMP 算法还得感谢好友的不吝赐教,再次感谢!人生中有 95% 的事不是我们自主可控的,我们争取做好这 5%,并且可以的话去支持一下别人,去支持一下别人的 95%。赠人玫瑰,手留余香。

文章修改: 2021年11月15日22:46

0

评论区