鲁迅说过，春节过后，依然要加强学习，不断提高自己。每天一道二哥的 LeetCode 刷题笔记，精神百倍。先用 String 的 indexOf() 方法实现方式来 strStr() 方法，然后再用 KMP 算法来实现一遍，酸爽极了。

题意

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

难度

简单

示例

例 1

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

例 2

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

分析 1

对于这道题，我们很容易想到 Java 字符串的indexOf()方法，我在二哥的 Java 进阶之路上也帮大家讲过这个方法的实现。

那题解立马就有了，嘿嘿 😜。

class Solution {
    public int strStr(String haystack, String needle) {
        int index = haystack.indexOf(needle);
        return index;
    }
}

并且题解效率非常高：

直接就击败 100% 的 Java 用户。

分析 2

不过 LeetCode 出这道题，显然不是为了让我们直接调用indexOf()方法，而是让我们去实现一个indexOf()方法。

既然如此，我们不妨再来看一下 indexOf 方法的源码（最终 indexOf(String str) 调用的方法）：

JDK8 版本的方法签名是：

static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex)

先来看参数：

• source：主字符串的字符数组。
• sourceOffset：主字符串的起始偏移量。
• sourceCount：主字符串中字符的总数。
• target：要查找的子字符串的字符数组。
• targetOffset：子字符串的起始偏移量。
• targetCount：子字符串中字符的总数。
• fromIndex：开始搜索的索引位置。

再来看逻辑流程：

• 首先，检查fromIndex是否大于或等于sourceCount。如果是，且targetCount为 0，则返回sourceCount；否则返回-1。
• 如果fromIndex小于 0，它被设置为 0。
• 如果targetCount为 0，则直接返回fromIndex，因为空字符串被认为存在于任何位置。
• 然后，计算最大搜索索引max，这是为了确保搜索时target能够完全位于source中。
• 接下来，遍历source数组，从sourceOffset + fromIndex开始，直到max，查找与target数组中第一个字符匹配的字符。
• 一旦找到第一个匹配的字符，就在source中从这个位置开始，尝试匹配整个target数组。
• 如果所有后续字符都匹配，就返回当前的索引（调整过的，即i - sourceOffset），因为这表示找到了完整的子字符串。
• 如果遍历完成后未找到匹配的子字符串，则返回-1。

这种实现方式在处理大字符串时效率不如KMP（Knuth-Morris-Pratt）算法，但 JDK 选择了这种更易于理解和实现的方法，足以处理大多数常见的情况。

所以，我们可以按照这个思路来实现我们的strStr()