【每日一题】28. Implement strStr()
【每日一题】28. Implement strStr()
公众号-不为谁写的歌
发布于 2020-07-31 15:58:29
发布于 2020-07-31 15:58:29
问题描述
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
题解
- 首先，考虑Corner case：needle字符串长度为0，此时按要求返回0.
- 正常情况下，使用两层循环，将needle字符串依次与haystack不同位置开始的与needle长度相同的子串进行比较。
- 外层循环次数为sizeA-sizeB；两者的长度差；
- 内层循环为sizeB，needle字符串的长度；
- 使用一个标志位flag，表示haystack中能否找到needle子串；找到，返回idx；没找到，继续找。
完整代码：
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
int sizeA = haystack.size(), sizeB = needle.size();
int idx = -1;
for (int i=0; i<= sizeA-sizeB; i++){
bool flag = true;
for (int j=0; j< sizeB; j++){
if (haystack[j+i] != needle[j]){
flag = false;
break;
}
}
if (flag){
idx = i;
break;
}
}
return idx;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录