[LeetCode解題攻略] 44. Wildcard Matching

題目描述

給定一個輸入字串 s 和一個Pattern p，其中：

• s 是輸入字串，只包含小寫字母。
• p 是匹配模式字串，可能包含以下特殊字元：
• • ? 可以匹配任何單個字元。
  • * 可以匹配任意長度（包括 0）的一段字元。

要求實現一個能夠支援字元* 和 ?的Wildcard Pattern Matching的函式。

範例 1：

輸入: s = "aa", p = "a"
輸出: false
解釋: "a" 只能匹配一個 'a'，而非兩個。

範例 2：

輸入: s = "aa", p = "*"
輸出: true
解釋: '*' 可以匹配任意字元序列。

範例 3：

輸入: s = "cb", p = "?a"
輸出: false
解釋: '?' 可以匹配 'c'，但 'a' 無法匹配 'b'。

解題思路

這題類似於正則表達式匹配，但難度更高，因為我們需要處理 * 和 ? 的匹配規則。根據問題特性，有以下幾種解法。

解法一：動態規劃

思路

1. 使用一個二維 DP 陣列 dp，其中 dp[i][j] 表示 s 的前 i 個字元與 p 的前 j 個字元是否匹配。
2. 初始化：
3. • dp[0][0] = True：空字串和空模式匹配。
   • dp[0][j] = True，當 p[1..j] 全是 * 時。
   • 其他情況初始化為 False。
3. 遞推公式：
4. • 如果 p[j-1] == s[i-1] 或 p[j-1] == '?'，則 dp[i][j] = dp[i-1][j-1]。
   • 如果 p[j-1] == '*'，則 dp[i][j] = dp[i-1][j] or dp[i][j-1]：dp[i-1][j] 表示 * 匹配多個字元。dp[i][j-1] 表示 * 匹配 0 個字元。
4. 返回結果：dp[len(s)][len(p)]。

程式碼

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        # 初始化 DP 陣列
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # 初始化 p 開頭為 '*' 的情況
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]

        # 填充 DP 陣列
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]

        return dp[m][n]

時間與空間複雜度

• 時間複雜度：O(m*n)，其中 m 是 s 的長度，n 是 p 的長度。
• 空間複雜度：O(m*n)，用於存儲 DP 陣列。

解法二：雙指針法

思路

1. 使用兩個指針：
2. • i 遍歷 s。
   • j 遍歷 p。
2. 記錄最近一次 * 出現的位置，以及當前匹配到的字串位置。
3. 當匹配失敗時，回溯到上一個 * 的位置，並嘗試擴展匹配的長度。
4. 如果模式中所有的 * 都被嘗試過，則匹配失敗。

程式碼

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        i = j = 0  # 指向 s 和 p 的指針
        star_index = -1
        match_index = 0

        while i < m:
            # 當字元匹配或遇到 '?' 時
            if j < n and (p[j] == s[i] or p[j] == '?'):
                i += 1
                j += 1
            # 遇到 '*'，記錄星號的位置，並假設它匹配 0 個字元
            elif j < n and p[j] == '*':
                star_index = j
                match_index = i
                j += 1
            # 匹配失敗但之前有星號，回溯到星號
            elif star_index != -1:
                j = star_index + 1
                match_index += 1
                i = match_index
            else:
                return False

        # 檢查剩餘的模式是否全是 '*'
        while j < n and p[j] == '*':
            j += 1

        return j == n

時間與空間複雜度

• 時間複雜度：O(m+n)，其中 m 是 s 的長度，n 是 p 的長度。
• 空間複雜度：O(1)，只使用常數空間。

結論

1. 如果需要簡潔高效的解法，雙指針法 是較好的選擇，適合處理大規模字串。
2. 如果對於邊界條件需要嚴格檢查，則使用 動態規劃，較為直觀且容易調試。
3. 這題的核心在於處理 * 和 ? 的靈活匹配，熟練掌握這些技巧後，類似題型的解法會更容易。

希望這篇解題教學對大家有幫助！