实现 strStr()
- 难度: 简单
- 通过率: 30.7%
- 题目链接:https://leetcode-cn.com/problems/implement-strstr
题目描述
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll" 输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明:
当 needle
是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle
是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解法:
面试中暴力解法就够了,本题最关键的是要细心。尤其是使用 C++ 来实现,存在很多坑。
class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack.size() < needle.size()) return -1;
for (int i = 0; i <= haystack.size() - needle.size(); i++) {
int j = 0;
while (j < needle.size() && needle[j] == haystack[i + j]) {
j++;
}
if (j == needle.size()){
return i;
}
}
return -1;
}
};
我第一次写出了下面这样的代码,出现了严重的 BUG。因为 haystack
可能比 needle
短,此时 haystack.size() - needle.size()
有可能会是负的,但是因为 size
返回的是无符号的数,因此发生了下溢。结果变成了一个非常大的正数。
for (int i = 0; i <= haystack.size() - needle.size(); i++){
}