題目出處

44. Wildcard Matching

難度

hard

個人範例程式碼

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        self.memo_matched_begin = {}
        return self.dfs(s, p, 0, 0)

    def dfs(self, s, p, start_s, start_p):
        if (start_s, start_p) in self.memo_matched_begin:
            return self.memo_matched_begin[(start_s, start_p)]

        # end of recursion
        if start_s >= len(s) and start_p >= len(p):
            return True
        if start_s < len(s) and start_p >= len(p): # s left
            return False        
        if start_s >= len(s) and start_p < len(p): # p left
            for idx in range(start_p, len(p)):
                if p[idx] == "*":
                    continue
                else:
                    return False
            return True

        # define and split
        if self.is_char_matched(s[start_s], p[start_p]): # normal pattern
            ans = self.dfs(s, p, start_s+1, start_p+1)
        elif p[start_p] == "*":
            # can be nothing to anything(keep *)
            # * = nothing, self.dfs(s, p, start_s, start_p+1)
            # * = anything, self.dfs(s, p, start_s+1, start_p)
            ans = self.dfs(s, p, start_s, start_p+1) or self.dfs(s, p, start_s+1, start_p)
        else:
            ans = False

        self.memo_matched_begin[(start_s, start_p)] = ans
        return ans

    def is_char_matched(self, s, p):
        return s == p or p == "?"

算法說明

超難的配對問題，首先我們先不管加速，嘗試先寫一個能解的版本

基本版的寫完後，就會發現簡單的都能 pass，比較難的 case 會 TLE，
原因是因為我們的搜索時間是「指數等級」的，看來是要稍微優化一下。

記憶化搜索 (DP)

我們用一個策略紀錄我們搜尋的結果，主要因為我們進行的「重複搜尋」太多了，
我們透過記憶 start_p, start_q 的兩個起始位置，與對應結果。

當遞迴再一次回到此位置時，直接去 hashtable 拿 (start_p, start_q) 的結果來用。

這邊我們強調一下增加的部分：

• 拿取

if (start_s, start_p) in self.memo_matched_begin:
    return self.memo_matched_begin[(start_s, start_p)]

• 儲存

self.memo_matched_begin[(start_s, start_p)] = ans

這個就是一種「以空間換取時間」的策略

於是我們就能完成這道 hard 的題目。

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

input handling

x

Boundary conditions

見上述說明

Reference

• 通配符匹配 · Wildcard Matching