程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Implement strStr()(Sunday算法)

LeetCode Implement strStr()(Sunday算法)

編輯:C++入門知識

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來獲得相關源碼。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved