python - 从给定的 str 中找到 str 第一次出现的索引

Question

Google 或 Amazone 在面试中问以下问题，我的解决方案会被接受吗？

问题:从给定字符串中找到给定单词第一次出现的索引

注意:上面的问题来自一个网站，下面的代码通过了所有的测试用例。但是，我不确定这是否是最佳解决方案，是否会被大巨头接受。

def strStr(A, B):
    if len(A) == 0 or len(B) == 0:
        return -1
    for i in range(len(A)):
        c = A[i:i+len(B)]
        if c == B:
            return i
    else:
        return -1

Answer 1

关于这个主题，您可以学习一些算法，例如

rabin karp algorithm , z algorithm , kmpalgorithm

它们都以 O(n+m) 的运行时复杂度运行，其中 n 是字符串长度，m 是模式长度。您的算法以 O(n*m) 运行时复杂度运行。我建议从 rabin karp 算法开始学习，我个人觉得它最容易掌握。

还有一些高级主题，比如在一个字符串中搜索多个模式，比如 aho-corasick 算法，很好读。我认为这就是 grep 在搜索多个模式时使用的。希望对您有所帮助:)