http://oj.leetcode.com/problems/implement-strstr/
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
大海捞针,很贴切,好吧,我用暴力居然直接过了,羞愧....
JDK源码中有实现,就不罗嗦了,下午研究了一下KMP算法(O(M + N)),很不错的算法,明天好好整理一下,重新写一遍,并写一篇关于KMP算法的博文吧。
暴力——O(m*n)代码如下:
public String strStr(String haystack, String needle) { if(needle == null || needle.length() == 0 || haystack == null){ return haystack; } int hayStackLen = haystack.length(); int needleLen = needle.length(); if(hayStackLen < needleLen || (hayStackLen == needleLen && !haystack.equals(needle))){ return null; } char first = needle.charAt(0); int max = hayStackLen - needleLen + 1; for(int i = 0; i < max; i++){ if(haystack.charAt(i) != first){ while(++i < max && haystack.charAt(i) != first); } if(i < max){ int j = i + 1; int end = j + needleLen - 1; for(int k = 1; j < end && needle.charAt(k) == haystack.charAt(j); j++,k++); if(j == end){ return haystack.substring(i); } } } return null; }
相关推荐
题目来源: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 ...