题目描述 实现str（）函数。
给定一个haystack字符串和一个needle字符串，在haystack字符串中找出needle字符串出现的第一个位置（从0开始）。如果不存在，则返回-1。
示例
输入: haystack = "hello", needle = "ll"
输出: 2我的思路 以haystack字符串为主，遍历haysack字符串分别以每个字符串为起点，嵌套遍历needle字符串，时间复杂度为O(m*n)。
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
if(needle.empty()){
return 0;
}
int i = 0;
int j = 0;
for(i=0;
i<=n-m;
i++){
bool flag = true;
for(j=0;
j更好的思路 可以考虑到灵活地使用substr函数，同样遍历haysack字符串分别以每个字符串为起点，截取needle大小的一段字符串分别与neddle字符串比较，减少了遍历neddle每一个字符串所花费的时间，时间复杂度O(n-m+1)。
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
if(n == 0)
return 0;
if(m < n)
return -1;
for(int i = 0;
i <= n - m;
i++){
string subStr = n.substr(i, m);
if(subStr == needle)
return i;
}
return -1;
}
};
【LeetCode - 实现strStr()】还有一种rolling hash的算法可以实现O(n)的时间复杂度具体参考rolling hash-Wikipedia。
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)