【字符串算法题记录】28. 找出字符串中第一个匹配项的下标

题目链接
这一题蛮简单，但是逻辑上容易忽略一些小细节。我一开始想的是从haystack数组的头开始找与needle匹配的第一个字符，然后再顺着看下面连续的字符是否匹配，然后直接返回结果，但是忽略了很重要的一点：haystack中可能有多个字符和needle的第一个字符是一样的，那么我们不能一次匹配就返回判断结果，而是要遍历整个haystack进行判断。

class Solution {
    public:
    int strStr(string haystack, string needle) {
        int j = 0;
        int index = -1;
        for(int i = 0; i < haystack.size(); i++) { 
            if(haystack[i] == needle[j]) {  // 首先在haystack中找到needle的第一个字符
                index = i;  // 并记录第一个匹配字符的下标index
                // 进入循环检查是否接下来每一个字符都是与needle匹配的
                while(haystack[i] == needle[j] && j < needle.size() && i < haystack.size()) {
                    i++;
                    j++;
                }
                if(j == needle.size()) return index; // 如果needle中的字符全检查完了，则是匹配的，返回对应的index
                else return -1; // 如果needle中的字符没有检查完，即不匹配，则返回-1
            }
        }
        return index; // for循环已经结束都没有返回的话，说明haystack中没有匹配字符，则返回-1
    }
};

第二次修改后的如下，但是还是错了，因为我直接用外层的for循环的变量i去做字符串匹配检查，这其中包含了i++指令，更改了i的值，那么会影响到最外层的for循环。

class Solution {
    public:
    int strStr(string haystack, string needle) {
        int index = -1; // index默认值是-1
        for(int i = 0; i < haystack.size(); i++) { 
            int j = 0;
            if(haystack[i] == needle[j]) {  // 首先在haystack中找到与needle匹配的第一个字符
                index = i;  // 并记录第一个匹配字符的下标index
                // 进入循环检查是否接下来每一个字符都是与needle匹配的
                while(haystack[i] == needle[j] && j < needle.size() && i < haystack.size()) {
                    i++;
                    j++; 
                }
                if(j == needle.size()) return index; // 如果needle中的字符全检查完了，则是匹配的，返回对应的index
                else index = -1; // 如果needle中的字符没有检查完，即不匹配，index要恢复默认值
            }
        }
        return index; // for循环已经结束都没有返回的话，说明haystack中没有匹配字符，则返回-1
    }
};

最终正确代码如下：

class Solution {
    public:
    int strStr(string haystack, string needle) {
        int index = -1; // index默认值是-1
        for(int i = 0; i < haystack.size(); i++) { 
            int j = 0;
            if(haystack[i] == needle[j]) {  // 首先在haystack中找到与needle匹配的第一个字符
                index = i;  // 并记录第一个匹配字符的下标index
                int k = i;  // 用k来代替i进行接下来的检查（不然i值被改变会影响最外层的for循环）
                
                // 进入循环检查是否接下来每一个字符都是与needle匹配的
                while(haystack[k] == needle[j] && j < needle.size() && k < haystack.size()) {
                    k++;
                    j++; 
                }
                if(j == needle.size()) return index; // 如果needle中的字符全检查完了，则是匹配的，返回对应的index
                else index = -1; // 如果needle中的字符没有检查完，即不匹配，index要恢复默认值
            }
        }
        return index; // for循环已经结束都没有返回的话，说明haystack中没有匹配字符，则返回-1
    }
};