LeetCode中每日一题28. 实现 strStr()的趣谈

1 题目描述

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

2 题目分析

这道题的暴力解法是逐个进行匹配查找是否是子串，看了一下题解中用到的是KMP优化的，具体的过程可学习官方题解，这里讲一下indexOf函数。因为这道题可以用一行代码
return haystack.indexOf(needle)实现，于是好奇点进去源码里面看了一下，发现源码用的方法是暴力解法。

3 源码如下

这里是根据题目要求翻译了一下。

private static int myIndexOf(String haystack, String needle) {
    char[] value = haystack.toCharArray();char[] str = needle.toCharArray();if (str.length == 0) return 0;if (value.length == 0) return -1;int m = value.length, n = str.length;char first = str[0];int max = m - n;for (int i = 0; i <= max; i++) {
    // 找到第一个与匹配的字符位置while (i <= max && value[i] != first) i++;// 找到第一个匹配的遍历之后的是否匹配if (i <= max) {
    int j = i + 1;int end = j + n - 1;for (int k = 1; j < end && value[j] == str[k]; j++, k++);if (j == end) {
    return i;}}}return -1;}

4 揣摩用意

刚开始看到这个源码的时候感觉有点不可思议，官网竟然没有用KMP算法来优化。想了一想感觉人家肯定是有用意的，比如代码通用性这一点就可以解释了。
用意

1. 增加代码通用性，首先查看源码的参数：byte[] value, int valueCount, byte[] str, int strCount, int fromIndex
   最后一个多了个fromIndex形参，显然这个函数可以从某个起点开始判断。
2. 牺牲时间换空间，在现在空间很大的情况下，我们往往都是牺牲空间换时间，当考虑Java刚出生的时候大多数情况宁愿去牺牲时间换空间，而KMP算法又需要额外的空间复杂度。