LeetCode 筆記：Wildcard Matching（通配符匹配）

一、題目描述

實現支持 ? 和 * 的通配符匹配：
? 匹配任意單字符
* 匹配任意字符序列（含空序列）
匹配需覆蓋整個字符串。

範例： isMatch("aa","a")=false; isMatch("aa","*")=true; isMatch("ab","?*")=true

二、解題思路：雙指針 + 回溯記錄

遞歸易超時。採用迭代：
- s_idx, p_idx 遍歷字符串 s 和模式 p。
- 遇到 * 記錄當前位置 star_idx (p中) 和 match_idx (s中)，p_idx++。
- 匹配失敗且曾有 *：回溯到 star_idx，令 * 多匹配一個字符（match_idx++），s_idx = match_idx, p_idx = star_idx + 1。
- 遍歷結束後，跳過 p 剩餘的 *，若 p 也結束則匹配成功。

三、代碼實現（C++）

class Solution {
public:
    bool isMatch(string s, string p) {
        int s_idx = 0, p_idx = 0;
        int star_idx = -1, match_idx = 0;
        while (s_idx < s.size()) {
            if (p_idx < p.size() && (p[p_idx] == '?' || p[p_idx] == s[s_idx])) {
                ++s_idx; ++p_idx;
            } else if (p_idx < p.size() && p[p_idx] == '*') {
                star_idx = p_idx;
                match_idx = s_idx;
                ++p_idx;
            } else if (star_idx != -1) {
                // 回溯：* 多匹配一個字符
                p_idx = star_idx + 1;
                s_idx = ++match_idx;
            } else {
                return false;
            }
        }
        while (p_idx < p.size() && p[p_idx] == '*') ++p_idx;
        return p_idx == p.size();
    }
};

四、複雜度分析

• 時間複雜度：O(N+M) 平均，最壞 O(N*M) (但實際極快)
• 空間複雜度：O(1)

此法避免了遞歸棧溢出和 DP 的 O(NM) 空間，工程上常用。