28.实现 strStr()

客官°小女子只卖身不卖艺 2022-09-11 06:10 142阅读 0赞

题目描述：

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例1：

输入：haystack = "hello", needle = "ll"
    输出：2

示例2：

输入：haystack = "aaaaa", needle = "bba"
    输出：-1

示例3：

输入：haystack = "", needle = ""
    输出：0

解题1：暴力法。将母串 heystack 和子串 needle 分别转换成数组，然后使用双层循环去逐个比较两个串中的元素，如果 heystack\[i\] == needle\[j\]，再去判断 heystack\[i + 1\] 是否等于 needle\[j + 1\]，直到将子串比较完毕，如果符合，直接返回 i 即可。

代码如下：

public static int strStr(String haystack, String needle) {
        char[] haystackArray = haystack.toCharArray();
        char[] needleArray = needle.toCharArray();
        for (int i = 0; i <= haystackArray.length - needleArray.length; i++) {
            int j;
            for (j = 0; j < needleArray.length; j++) {
                if (haystackArray[i + j] != needleArray[j]) {
                    break;
                }
            }
            if (j == needleArray.length) {
                return i;
            }
        }
        return -1;
    }

假设母串 heystack = "hello"，子串needle = "ll"，其循环过程如下：

第一次：i = 0，j = 0，heystack\[i\] = 'h'，needle\[j\] = 'l'，heystack\[i + j\] != needle\[j\]，break 跳出内层循环，此时 j != needle.length，进入第二次循环

第二次：i = 1，j = 0，heystack\[i\] = 'e'，needle\[j\] = 'l'，heystack\[i + j\] != needle\[j\]，break 跳出内层循环，此时 j != needle.length，进入第三次循环

第三次：i = 2，j = 0，heystack\[i\] = 'l'，needle\[j\] = 'l'，heystack\[i + j\] == needle\[j\]，继续内层循环，j 自增 1，needle\[j\] = 'l'，heystack\[i + j\] == needle\[j\]，继续去内层循环，此时 j 自增 1 之后等于 2，不满足内层循环条件，所以退出内层循环，此时 j == needle.length，即找到了子串在母串中的位置了，直接 return 即可

解题2：双指针法。基本思路和暴力解法一样。

代码如下：

public static int strStr2(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int left = 0, right = 0, index = 0;
        while (right < haystack.length() && index < needle.length()) {
            if (haystack.charAt(right) != needle.charAt(index)) {
                left++;
                right = left;
                index = 0;
            } else {
                right++;
                index++;
            }
        }
        return index == needle.length() ? left : -1;
    }

解题3：直接使用 str.indexOf() 方法

public static int strStr3(String haystack, String needle) {
        return haystack.indexOf(needle);
    }