LeetCode每日一题：实现strStr()

链接: 实现strStr()

---

这道题有点像实现函数strcmp()差不多，只不过这里有个难点，就是如果haystack中有多个字符和与needle中的第一个字符相同，并且要是这前几个相同的字符后的字符串与needle不相同，则要重新判断。
所以这里的思路是用四个指针，其中两个是函数的形参，所以我们要再创建两个指针，分别指向haystack和needle。

	//若为空直接返回0
    if (haystack == NULL)
        return 0;
    //求出两个字符串的长度
    int haystacklen = strlen(haystack);
    int needlelen = strlen(needle);
    //needle的长度大于haystack，则直接返回-1
    if(haystacklen < needlelen)
        return -1;
    //开辟两个指针
    char* ph = haystack;
    char* pn = needle;
1
2
3
4
5
6
7
8
9
10
11
12

接着就是进入循环的部分：
对haystack的长度进行循环，然后判断*ph是否等于 needle的第一个字符，若不相等则直接 ph向后走一步。
若两个字符相等，则先保留住这个ph的位置，以防等会判断两个字符串不一致时候，返回时找不到原位置，所以 把haystack移到ph的位置。接着开始 对pn的长度循环，若两个 ph和 pn在每个位移的字符都相等，则退出循环后直接返回 i 的值，若不相等了就将 ph移到原来haystack的位置，然后 pn回到needle的位置，然后 break出来，继续循环，直到长度结束。

	int flag = 1;
    int i = 0;
    for(i = 0; i < haystacklen; i++)
    {
        if(*ph != *pn)
        {
            ph++;
        }
        else
        {
            haystack = ph;
            for(int j = 0; j < needlelen; j++)
            {
                if(*ph == *pn)
                {
                    ph++;
                    pn++;
                    flag = 0;
                }
                else
                {
                    ph = haystack;
                    ph++;
                    pn = needle;
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                return i;
        }
    }
        return -1;
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
30
31
32
33

完整的代码：

int strStr(char * haystack, char * needle){
    if (haystack == NULL)
        return 0;
    //求出两个字符串的长度
    int haystacklen = strlen(haystack);
    int needlelen = strlen(needle);
    //needle的长度大于haystack，则直接返回-1
    if(haystacklen < needlelen)
        return -1;
    //开辟两个指针
    char* ph = haystack;
    char* pn = needle;
    
    int flag = 1;
    int i = 0;
    for(i = 0; i < haystacklen; i++)
    {
        if(*ph != *pn)
        {
            ph++;
        }
        else
        {
            haystack = ph;
            for(int j = 0; j < needlelen; j++)
            {
                if(*ph == *pn)
                {
                    ph++;
                    pn++;
                    flag = 0;
                }
                else
                {
                    ph = haystack;
                    ph++;
                    pn = needle;
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                return i;
        }
    }
        return -1;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47