Fork me on GitHub

leetcode之28. 实现strStr()

发表于 | 分类于
字数统计 679 字 | 阅读时长 2 分钟

题目描述：

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

1
2
3
> 输入: haystack = "hello", needle = "ll"
> 输出: 2
>

示例 2:

1
2
3
> 输入: haystack = "aaaaa", needle = "bba"
> 输出: -1
>

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()) 定义相符。

解题思路：

思路一：

时间复杂度：$O(n^2)$，空间复杂度：$O(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
class Solution {
public:
    int strStr(string haystack, string needle) {
        
        if(needle.size() == 0) return 0;
        if(haystack.size() < needle.size()) return -1;
        // 需要先把string转成指针，因为注意这里的转换方式，和转换的类型
        // 必须是const char 类型，.data()和.c_str()都可以
        const char *p = haystack.data();
        const char *q = needle.c_str();
        int i = 0;
        int j = 0;
        // 注意这里控制的边界条件，第一个字符的长度减去第二个字符的长度+1，因为，
        // 每次都要匹配第二个字符的长度，所以i的边界需要控制一下，画图就明白了
        for(;i < haystack.size() - needle.size() + 1;i++)
        {
                // 设置一个标志位，默认假设第二个字符串能匹配第一个字符串
                bool is_no = true;
                // 对第二个字符串开始遍历，判断是否和第一个字符串都匹配
                for(j = 0; j < needle.size();j++)
                {
                        // 注意这里的访问方式，是采用指针的访问方式
                        // 等同于p[i+j] q[j]
                        // 如果某个字符不想等，那么标志位记为false
                        if(*(p + i + j) != *(q + j))
                        {
                                is_no = false;
                                // 并且退出
                                break;
                        }
                }
                // 每次匹配完毕，检测是否匹配成功，如果成功就直接返回匹配的位置
                if(is_no)
                {
                        // cout << i << endl;
                        return i;
                }
                // 不成功，从下一个字符接着匹配
        }
        return -1;
    }      
};

思路二：

如果，你对某个结构(数组，字典，链表等)做了修改（增加，删除）的操作，那么，这种情况需要考虑用指针，如果，只是对某个结构做查询操作，那么用下标访问就可以了

时间复杂度：$O(n^2)$, 空间复杂度：$O(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
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length() == 0) return 0;
        if(haystack.length() == 0) return -1;
        if(haystack.length() < needle.length() ) return -1;
        for(int i = 0; i < (haystack.length() - needle.length() + 1); i++)
        { 
          bool flag = true;
          for(int j = 0; j < needle.length(); j++)
          {
            if(haystack[i+j] != needle[j])
            {
              
              flag = false;
              break;
            }
          }
          if(flag)
          {     	
          	return i;
          }
        }
     return -1;       
    }
};