leetcode-28. 实现 strStr()

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