28. Implement strStr()

case1(KMP):

  1. 两个指针 i,j 分别指向母串 h 和子串 n
  2. 如果 h[i] == n[j] 则母串和子串同时开始移动下标进行比值
  3. 如果不相等 i 归为上一次母串和子串相等的下标 + 1,j 则归为 0
  4. 当 i 或 j 大于母串子串的长度的时候,跳出循环
  5. 根据 j 的值判断结果
    class Solution(object):
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         i , j = 0 , 0
         h = list(haystack)
         n = list(needle)
         while i < len(h) and j < len(n):
             if h[i]==n[j]:
                 i += 1;
                 j += 1;
             else:
                 i = i - j + 1
                 j = 0
         if j == len(needle):
             return i - j
         return -1
    

case2:

  1. 循环求解
  2. 使用 list 切片
    class Solution(object):
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if needle == "":
             return 0
         h = list(haystack)
         n = list(needle)
         for i in range(len(h)):
             if h[i] == n[0] and h[i: len(n) + i] == n:
                 return i
         return -1
    

594 (lintcode) Implement strStr function in O(n + m) time.

strStr return the first index of the target string in a source string. The length of the target string is m and the length of the source string is n.
If target does not exist in source, just return -1.

class Solution:
    """
    @param: source: A source string
    @param: target: A target string
    @return: An integer as index
    """
    def strStr2(self, haystack, needle):
        if haystack == None or needle == None:
            return -1
        #generate next array, need O(n) time
        i, j, m, n = -1, 0, len(haystack), len(needle)
        next = [-1] * n
        while j < n - 1:  
            #needle[k] stands for prefix, neelde[j] stands for postfix
            if i == -1 or needle[i] == needle[j]:   
                i, j = i + 1, j + 1
                next[j] = i
            else:
                i = next[i]
        #check through the haystack using next, need O(m) time
        i = j = 0
        while i < m and j < n:
            if j == -1 or haystack[i] == needle[j]:
                i, j = i + 1, j + 1
            else:
                j = next[j]
        if j == n:
            return i - j
        return -1

参考链接:
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
https://leetcode.com/problems/implement-strstr/discuss/13237/Java-and-Python-solution-using-KMP-with-O(m-%2B-n)-time-complexity


请多多指教。

文章标题:28. Implement strStr()

本文作者:顺强

发布时间:2019-12-27, 23:59:00

原始链接:http://shunqiang.ml/leetcode-28-implement-str/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏