LeetCode Implement strStr()（Sunday算法）

實現字符串子串匹配函數strStr()。如果字符串A是字符串B的子串，則返回A在B中首次出現的地址，否則返回-1。

注意點：

- 空字符串是所有字符串的子串，返回0

例子：

輸入: haystack = “abc”, needle = “bc”
輸出: 1

輸入: haystack = “abc”, needle = “gd”
輸出: -1

解題思路

字符串匹配常見的算法是KMP，不過感覺該算法理解困難，效率也不是特別高。我用了Sunday算法來實現字符串的匹配。大體思路如下：

被搜索的字符串是”abcdefg”，要搜索的字符串是”ef”

 abcdefg
 ef

如果當前不匹配，則判斷當前嘗試匹配的後一位，即”c”是否在要搜索的字符串中，如果不在，則要搜索的字符串直接後移它自己的長度+1。

 abcdefg
    ef

如果存在，如此時”f”在”ef”中，則把該位置對齊。

 abcdefg
     ef

匹配成功返回結果。

AC源碼

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0
        if not haystack:
            return -1
        i = 0
        needleLength = len(needle)
        while i < len(haystack):
            if haystack[i:i + needleLength] == needle:
                return i
            else:
                index = 0
                try:
                    index = needle.rindex(haystack[i + needleLength])
                except Exception:
                    i += needleLength + 1
                i += needleLength-index
        return -1


if __name__ == "__main__":
    assert Solution().strStr("abcdefg", "ab") == 0
    assert Solution().strStr("abcdefg", "bc") == 1
    assert Solution().strStr("abcdefg", "cd") == 2
    assert Solution().strStr("abcdefg", "fg") == 5
    assert Solution().strStr("abcdefg", "bcf") == -1

歡迎查看我的Github來獲得相關源碼。