一、LeetCode 题库的第 28 题——实现strStr()

题目如下：

二、解题代码

该题就是两层循环，第一层循环主要是遍历字符串，第二层循环用来进行匹配。实现代码如下：

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

    int i, n, j;
    if (str2len == 0) {
        return 0;
    }

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

以上是我的解题代码，就是使用两层来进行实现，没有太好的思路，所以解题思路就没什么可说的了。上面的代码，其实还可以减少循环的次数，但是会增加一些代码量，LeetCode 对以上代码执行的时间显示为 1800 多毫秒。那么就增加一个判断，让循环次数少一些，增加的代码如下：

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

看上面的代码，只是在第一层的 for 循环中增加了一个判断，但是 LeetCode 给出的执行时间是 0 毫秒，是不是很惊人？为什么会这样呢？原因其实很简单，当 needle 很短的时候这个判断是没有太大差别的，但是当 needle 特别长的时候，减少的循环次数就非常明显了。