`

Leetcode - Implement strStr()

 
阅读更多

Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

[分析] 经典的字符查找问题,有四种经典解法, 暴力法,hash法,Boyer-Moorer算法和KMP算法。leetcode上分析指出面试时写出暴力法即可,关键是暴力法代码要写得clean。 实现1采用two pointer 方式,代码上不如实现1.1 clean。两者算法复杂度均为O(n * m)。 实现2 是一种个人认为最容易理解的O(n)算法,叫rolling hash算法,基本思想是利用一个hashcode表示一个字符串,对比长度等于代匹配串的子串的hash是否和待匹配串的hash值相等来查找,为防止溢出使用long表示hashcode。

[ref]
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://blog.csdn.net/kenden23/article/details/17029625


[code="java"]// Method 2: rolling hash, O(m + n - m)
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || haystack.length()  right)
                    return i;
                else
                    i++;
            }
            return -1;
        } else {
            return -1;
        }
    }
分享到:
评论

相关推荐

    c语言-leetcode 0028-implement-strstr.zip

    c c语言_leetcode 0028_implement_strstr.zip

    C语言-leetcode题解之28-implement-strstr.c

    c语言入门 C语言_leetcode题解之28-implement-strstr.c

    js-leetcode题解之28-implement-strStr().js

    js js_leetcode题解之28-implement-strStr().js

    _leetcode-python.pdf

    - Implement strStr(): 实现字符串的查找功能,类似于C语言中的strstr()函数。 - Divide Two Integers: 实现整数除法,不能使用乘法、除法和模运算符。 - Search in Rotated Sorted Array: 在旋转过的排序数组中进行...

    leetcode跳动问题-Implement-strStr:实现strStr()。返回`haystack`中第一次出现`needle`的索引,

    strStr-fail-fast.js的解决方案,也使用了自顶向下的迭代方法,但被设计为在遇到边缘情况时快速下降。 这提高了性能,几乎 100% 击败了之前所有的 Leetcode 提交。 示例 1: Input: haystack = "hello", needle = ...

    Leetcode-Algorithm-Exercise

    1_TwoSum 9_PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_Search...

    leetcode2-code_interview:LeetCodeLintCode题解,剑指offer题目,互联网公司面试,BAT外企等面试题

    Implement strStr() 实现找字串功能 lint158 anagrams 两个乱序字符串的比较 lint55 compare-string和group string都是同型题目 int79-LCS lintcode上的79题 寻找最长公共字串 lintcode 138-Subarray-Sum integer-...

    leetcode信封-LeetCode:LeetCode解题

    ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote...

    Leetcode扑克-leetcode:Leetcode算法实践

    Leetcode扑克 Leetcode Starting from 2020/08/02 Leetcode practice with Python ...Implement strStr() 实现 strStr() String / 字符串 循环遍历即可 algorithm-pattern: quick start 43 Multiply S

    leetcode答案-exercise-book:算法练习记录

    Implement strStr() 解决方法:KMP 2018-08-22 20:05 LeetCode: 57. Insert Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解...

    leetcode中国-leetcode:leetcode刷题

    Implement strStr() String to Integer (atoi) addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号...

    leetcode516-Lcode:代码

    leetcode 516 8/13 - 8/18 周:leetcode#: 409. longestPalindrome ...Implement strStr() 5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    LeetCode 28. 实现 strStr()

    LeetCode 的第 28 题“实现 strStr()”是一个经典的字符串搜索问题,要求我们在给定的字符串(haystack)中查找另一个字符串(needle)首次出现的位置。如果找不到,返回 -1。这个题目旨在考察对字符串处理的理解和...

    leetcode530-algorithm:算法

    leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring ...Implement strStr() 031 Next Permutat

    leetcode分类-leetcode:leetcode

    比如,实现strStr()函数(Implement strStr())和有效的括号(Valid Parentheses)等,需要深入理解字符串操作和正则表达式。 6. **哈希表**:哈希表提供高效的查找和插入操作,常用于解决查找重复项、最近点对等...

    算法刷题笔记leetcode/lintcode

    - Implement strStr(实现strStr函数) - Two Strings Are Anagrams(两个字符串是否为字母异位词) - Compare Strings(比较字符串) - Group Anagrams(字母异位词分组) - Longest Common Substring(最长...

    997leetcodec-myleetcode:我的leetcode解决方案

    28-implement-strstr.c 知识管理计划(完成)和 Boyer-Moore 算法。 使用 manacher 算法更新 5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-...

    LeetCode 刷题汇总1

    * 实现strStr()(Implement strStr()):实现字符串搜索算法。 7. 排序和搜索: * 合并两个排序列表(Merge Two Sorted Lists):合并两个排序列表。 * 搜索插入位置(Search Insert Position):在排序数组中...

Global site tag (gtag.js) - Google Analytics