LeetCode 通配符匹配：回溯法解決 * 與 ? 模式匹配

題目描述

實現支持 ? 和 * 的通配符匹配：

• ? 匹配任意單個字符
• * 匹配任意長度字符串（含空串）
• 要求完全匹配整個目標字符串，而非部分匹配

範例：

輸入: s = "abc", p = "a*b*e"
輸出: false

解題思路：雙指針 + 回溯（貪心 + 回退）

動態規劃雖正確但易超時。觀察 * 的特性：它可以匹配 0 個或多個字符。我們採用貪心策略：

1. 雙指針 s_idx、p_idx 同步遍歷
2. 字符相等或模式為 ?：雙指針前進
3. 遇到 *：記錄當前 s_idx 和 p_idx + 1（假設 * 匹配 0 字符），p_idx 前進
4. 不匹配且之前有 *：回退到記錄位置，s_idx 後移一位（讓 * 多匹配一字符），p_idx 恢復到 * 後
5. 不匹配且無 * 可用：直接返回 false
6. 目標串遍歷完後，檢查模式串剩餘是否全為 *

時間複雜度：O(m × n) 最壞情況，實際常近似 O(m + n)；空間複雜度：O(1)。

Python 參考實現

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        s_idx = p_idx = 0
        last_s_idx = last_p_idx = -1  # 記錄最後一次 * 的位置
        
        while s_idx < len(s):
            # 正常匹配（含 ?）
            if p_idx < len(p) and (s[s_idx] == p[p_idx] or p[p_idx] == '?'):
                s_idx += 1
                p_idx += 1
            # 遇到 *
            elif p_idx < len(p) and p[p_idx] == '*':
                p_idx += 1
                last_s_idx = s_idx
                last_p_idx = p_idx
            # 不匹配但有 * 可回退
            elif last_p_idx != -1:
                last_s_idx += 1
                s_idx = last_s_idx
                p_idx = last_p_idx
            # 完全不匹配
            else:
                return False
        
        # 檢查模式串剩餘是否全為 *
        while p_idx < len(p) and p[p_idx] == '*':
            p_idx += 1
        
        return p_idx == len(p)

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.isMatch("aa", "a") == False
    assert sol.isMatch("aa", "aa") == True
    assert sol.isMatch("aaa", "aa") == False
    assert sol.isMatch("aa", "*") == True
    assert sol.isMatch("aa", "a*") == True
    assert sol.isMatch("ab", "?*") == True
    assert sol.isMatch("aab", "c*a*b") == False
    print("所有測試通過")

核心要點總結

• 貪心 + 回溯：* 優先匹配 0 字符，失敗時回退多匹配一個
• 狀態記錄：只需記錄最後一個 * 的位置，無需棧或遞歸
• 完全匹配：目標串遍歷完後，模式串必須也遍歷完（或只剩 *）
• 對比正則：同類問題 Regular Expression Matching 但通配符規則不同

這種雙指針回溯法是解決通配符匹配的經典高效解法，掌握其「記錄、假設、回退」三步曲核心邏輯。