Question:
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, ornullif needle is not part of haystack.
Anwser 1: O(n*m)
class Solution {
public:
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int haylen = strlen(haystack);
int needlen = strlen(needle);
for(int i = 0; i <= haylen - needlen; i++){
char *p = haystack + i;
char *q = needle;
while(*q != '\0'){
if(*p != *q){
break;
} else {
p++;
q++;
}
}
if(*q == '\0'){
return haystack + i;
}
}
return NULL;
}
};
Anwser 2: O(n + m) KMP
class Solution {
public:
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int haylen = strlen(haystack);
int needlen = strlen(needle);
int* fail = new int[needlen];
memset(fail, -1, needlen * sizeof(int)); // strlen(fail)
int i, j, k;
for (i = 1; i < needlen; ++i) {
for (k = fail[i-1]; k >= 0 && needle[i] != needle[k+1]; k = fail[k]);
if (needle[k+1] == needle[i])
fail[i] = k + 1;
}
i = j = 0;
while(i < haylen && j < needlen) // while(haystack[i] && needle[j])
{
if (haystack[i] == needle[j])
{
++i;
++j;
}
else if(j == 0) ++i;
else j = fail[j-1] + 1;
}
delete fail;
/*
if (needle[j]) {
return NULL;
} else {
return haystack + i - j;
}*/
if(j == needlen){
return haystack + i - j;
} else {
return NULL;
}
}
};
参考推荐:
KMP字符串匹配算法
分享到:
相关推荐
题目来源:https://leetcode-cn.com/problems/implement-strstr 题目 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。...
ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote...
leetcode跳动问题实现 strStr() 实现strStr() 。 返回 haystack 中第一次出现 Needle 的索引,如果needle不是haystack一部分,则返回-1 。 澄清: 当needle为空字符串时,我们应该返回什么? 这是面试时要问的一个很...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
Leetcode扑克 Leetcode Starting from 2020/08/02 Leetcode practice with Python ...Implement strStr() 实现 strStr() String / 字符串 循环遍历即可 algorithm-pattern: quick start 43 Multiply S
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring ...Implement strStr() 3
Implement strStr() String to Integer (atoi) addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号...
leetcode 516 8/13 - 8/18 周:leetcode#: 409. longestPalindrome ...Implement strStr() 5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:
Implement strStr() 解决方法:KMP 2018-08-22 20:05 LeetCode: 57. Insert Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring ...Implement strStr() 031 Next Permutat
Implement strStr() 实现找字串功能 lint158 anagrams 两个乱序字符串的比较 lint55 compare-string和group string都是同型题目 int79-LCS lintcode上的79题 寻找最长公共字串 lintcode 138-Subarray-Sum integer-...
1_TwoSum 9_PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_Search...
28.Implement Strstr() KMP Hash BruteForce 35.Search Insert Position 二分法化简 2018/04/18: 29.Divide Two Integers 二进制累加代替除法,防止溢出 36.Valid Sudoku set去重复 2018/04/19: 038.Count and Say ...
28-implement-strstr.c 知识管理计划(完成)和 Boyer-Moore 算法。 使用 manacher 算法更新 5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-...
问题 完全的 017_Letter_Combinations_of_a_Phone_Number 018_4总和 019_Remove_Nth_Node_From_End_of_List ... 028_Implement_strStr() 029_Divide_Two_Integers 030_Substring_with_Concatenation_of
Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression Matching Wildcard Matching Longest Common Prefix Valid Number Integer to Roman Roman to Integer ...