一、前记(2/3)

浑浑噩噩,感觉每天的时间都不够用,到了12点总结的时候,发现还有一些题没做,还有一些东西没背(太烦!!)。数学题每天花上2,3个小时只能写上40道题左右,这在考研考试的时候怎么够用呢?单词背了就忘,好像每天都在和遗忘打仗。今天尝试着听了一下徐涛老师的考研政治,全程就是:我是谁?我在哪里?我在干嘛?如果到了后面还是这样不太好的复习状态,那可能会暂停一下“算法大挑战”这个系列。

二、题目描述

在这道题里面要注意几个点:1、haystack里面的有完整的needle字符串,而不是零散的字符。2、空字符串返回的结果是0。3、不存在相匹配的字符串返回的结果为-1.

三、解题思路

1、我的思路

其实我的思路比较简单:首先只能循环查找len(haystack)-len(needle)次,因为我们需要找到的是“在haystack里面完整的needle字符串”。并且如果我们找到haystack里面有一个字符与needle的第一个字符相同。那么我们可以看是否haystack[i+len(needle)]==needle。如果相等就返回i,不相等的话继续寻找,最终完成循环。

#encoding:utf-8
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i=0
        if len(needle)==0:  #如果为空字符串
            return 0
        n=len(needle)
        for i in range(len(haystack)-n+1):
            if haystack[i:i+n]==needle: #是否相等
                return i
            else:
                i+=1
        if i>(len(haystack)-n): #完成循环
            return -1
#as a checking
solution=Solution()
a="aaaaa"
b="bba"
print(solution.strStr(a,b))

2、别人的思路(KMP算法)

在学习别人的思路的时候,我看到一个非常有意思的名称叫做“KMP算法”,相当于是一种字符串查找方法。我这里不再详述,俺觉得阮一峰就讲的很清楚。

参考代码:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "":
            return 0

        # generate pnext
        i, k, m = 0, -1, len(needle)
        pnext = [-1] * m
        while i < m - 1:
            if k == -1 or needle[i] == needle[k]:
                i, k = i + 1, k + 1
                if needle[i] == needle[k]:
                    pnext[i] = pnext[k]
                else:
                    pnext[i] = k
            else:
                k = pnext[k]

        # matching
        h, j = 0, 0
        n = len(haystack)
        while h < m and j < n:
            if h == -1 or needle[h] == haystack[j]:
                h, j = h + 1, j + 1
            else:
                h = pnext[h]
        if h == m:
            return j - h
        return -1

四、学到了什么?

1、一个非常棒的KMP字符串查找方法