710 - Python LeetCode

【Leetcode】python - [28] Implement strStr() 個人解法筆記 | 內含 python None 的整理

題目出處

28. Implement strStr()

難度

easy

個人範例程式碼

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if haystack <mark> None or needle </mark> None: # input handling
            return -1

        for i in range(len(haystack)-len(needle)+1): # bounding, O(n)
            if (self.compare_strstr(haystack[i:i+len(needle)], needle)):
                return i

        return -1

    def compare_strstr(self, part_of_haystack, needle): # O(m)
        return part_of_haystack == needle

算法說明

字串比對字串，很簡單的處理

(最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解)

input handling

注意沒有輸入的時候的處理，
這裡要特別小心，「if not X」，會因為在Python中，None、False、0、""(空字符串)、、()(空元組)、{}(空字典) 都相當於 False 而出錯，
我們需要特別抓出「None」來判斷，因此我們必須要寫

if haystack <mark> None or needle </mark> None: # input handling

而不能寫

if not haystack or not needle:

Boundary conditions

本題最小的搜尋範圍為 len(source) - len(target)，
而因為 range 的語法關係，有 upper bounding 需要 +1

因此範圍為 「for i in range(len(haystack)-len(needle)+1): # bounding, O(n)」

補充 - 此題最佳算法為 KMP 演算法 O(n)

我上述舉的例子為 O(mn)，但這題的最佳作法為 KMP 演算法，
但由於目前階段還沒有想要鑽研特定項目到太深，這個特殊作法日後再來補

Reference