LeetCode | 28.实现strStr()

这次来写一下 LeetCode 的第 28 题，实现 strStr()。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

上面的题就是 实现 strStr() 题目的截图，同时 LeetCode 给出了一个函数的定义，然后要求实现 strStr() 的函数体。函数定义如下：

int strStr(char * haystack, char * needle){
}

这个题目就是一个简单的字符串工具库中的函数的实现，该函数中有两个参数，分别是两个字符串的指针。

问题分析

该题目就是字符串的匹配，我考虑的是比较简单的一种方式，两层循环进行匹配，外层循环是从 haystack 的第一个位置开始匹配，匹配的次数是 haystack 的长度减去 needle 的长度，内层循环则是从 haystack 的当前字符开始与 needle 进行匹配，如果匹配的每个字符都相等，则在全部匹配完之后则返回 haystack 当前匹配的位置（也就是外层循环中 haystack 的当前位置），如果匹配的过程中有不相等的字符，则直接进入 haystack 下一轮的匹配。

题目中要求，如果 haystack 中不存在 needle 则返回 -1；

如果，needle 是空字符串则返回 0；

这两种情况是要进行处理的。

看一下外层循环，为什么是 haystack 的长度减去 needle 的长度的次数，如下图：

haystack 中保存的字符串 hello 的长度是 5，needle 中保存的字符串 lo 的长度是 2，那么我们的外层循环的次数就是 5 - 2 = 3 次，当然是从 0 开始循环（0 到 3 实际是 4 次）。为什么是 3 次，因为当 haystack 的下标为 3 时，haystack 的剩余字符串个数已经和 needle 字符串的个数相同了，后面无论还有多少，都不用再循环了，因为剩余的 haystack 的字符串个数一定少于 needle 字符串的字符个数的情况下，绝对不会匹配成功的。

内层循环所要做的，就是逐个字符进行比较，这个没什么好说的。

代码实现

strStr() 的实现代码如下：

int strStr(char* haystack, char* needle) {
    int str1len = strlen(haystack);
    int str2len = strlen(needle);

    int i, n, j;

    if (str2len == 0) {
        return 0;
    }

    int len = str1len - str2len;

    for (i = 0; i <= len; i ++) {
        // 从i开始往后递增，如果全匹配则返回i
        n = i;

        for (j = 0; j < str2len; j ++) {
            if (haystack[n++] == needle[j]) {
                if (j == str2len - 1) {
                    return i;
                }
            } else {
                break;
            }
        }
    }

    return -1;
}

提交结果

在写完 strStr 函数体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。我们以上代码 “提交” 以后的截图如下：