28.找出字符串中第一个匹配项的下标

点击标题可直达LeetCode对应的题页

题目原文

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

思路

  • 内置函数(C++)
    在题解看到的，没错直接使用C++的find函数，不过这道题应该不是考察这个吧？

  • 暴力匹配
    一个一个字符进行比较

内置函数代码

1
2
3
4
5
6
class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

暴力匹配代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int strStr(char * haystack, char * needle){
    char *p = haystack;
    char *q = needle;

    while(*p != '\0')
    {
        if(*p == *q)
        {
            char* tmp_p = p;
            char* tmp_q = q;
            int start = p - haystack;
            while(*tmp_q != '\0')   //匹配整个needle字符串
            {
                if(*tmp_p != *tmp_q || *tmp_p == '\0')
                {
                    break;
                }
                tmp_p++;
                tmp_q++;
            }
            if(*tmp_q == '\0')
            {
                return start;
            }
        }
        p++;
    }
    return -1;
}

更简洁的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int strStr(char * haystack, char * needle)
{
    for(int i = 0;haystack[i] != '\0'; i++)
    {
        int j = 0;  //相当于指针，一个指针同时控制两个字符串的匹配遍历
        while(needle[j] != '\0' && haystack[i+j] != '\0' && haystack[i+j] == needle[j])   // 三个条件
        {                             // 1.needle没遍历完
            j++;                      // 2.haystack没遍历完 
        }                             // 3.两个字符串字符相等

        if(needle[j] == '\0')         //needle遍历完了
        {                             //说明在haystack中找到了needle  
            return i;                 //此时i就是开始的下标
        }
    }
    return -1;
}