Leetcode 28问题为什么我的strStr（）失败了？

Question

我试图解决这个leetcode问题：https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/885/

其思想是，您编写的代码可以在字符串中找到子字符串。为了练习，我正在（或至少曾经）尽可能以最有效的方式做这件事。我认为它可以在一个“for”循环中完成（希望只需要O（n）个时间）

这是我的密码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        needle = list(needle)
        haystack = list(haystack)
        goodPos = None
        goodCounter = 0
        if len(needle) == 0:
            return 0
        if len(haystack) == 0 or len(needle) > len(haystack):
            return -1
        for key, value in enumerate(haystack):
            if needle[goodCounter] != value:
                print(f"{needle[goodCounter]} does not match {value}, resetting")
                goodPos = None
                goodCounter = 0
            if needle[goodCounter] == value:
                print(f"We have a match at {value}")
                if goodCounter == 0:
                    print(f"We are setting the key at {key}")
                    goodPos = key
                goodCounter += 1
            if len(needle) == goodCounter:
                return goodPos
        print("Finished for loop")
        print(f"goodPos at {goodPos}")
        print(f"goodCounter at {goodCounter}")
        #For situations where we didnt caught it
        if goodCounter == len(haystack):
            return len(haystack)
        return -1

我被通过的73/79测试用例卡住了。特别是在这种输入下

Input: "mississippi" (substring: "issip")
My output: -1
Expected Output: 4

为什么我的代码不起作用，我有点被卡住了

Answer 1

以下是我运行您的代码时得到的结果：

key,value,goodPos,goodCounter
0  ,m    ,None   ,0
1  ,i    ,None   ,0
2  ,s    ,1      ,1
3  ,s    ,1      ,2
4  ,i    ,1      ,3
5  ,s    ,1      ,4
6  ,s    ,None   ,0
7  ,i    ,None   ,0
8  ,p    ,7      ,1
9  ,p    ,None   ,0
10 ,i    ,None   ,0

他们的密钥不断增加，当它意识到keyPos=1不是一个完整的匹配时，密钥已经被设置为位置7，此时找到匹配已经太晚了。我想你需要一个嵌套的for循环

编辑：

我决定亲自尝试一下，下面是我想出的for循环：

    for key, value in enumerate(haystack):
        if needle[0] == value:
            goodPos = key
            for key, value in enumerate(needle):
                if (len(haystack) - goodPos) < len(needle):
                    print('Needle went past end of haystack. No match found')
                    return -1
                if value == haystack[goodPos + key]:
                    goodCounter += 1
                    if len(needle) == goodCounter:
                        print('Match found at goodPos = ', goodPos)
                        return goodPos
                else:
                    goodCounter = 0
        else:
            goodPos = ''
            goodCounter = 0