LeetCode Wildcard Matching：雙指針貪心匹配通配符

通配符匹配：線性時間雙指針算法

實現支持 '?'（匹配任意單字符）和 '*'（匹配任意序列含空）的模式匹配。需完全匹配整個輸入字符串。

核心算法：記錄星號位置回溯

雙指針 i 遍歷字符串 s，j 遍歷模式 p。遇到 '*' 記錄位置 starIdx = j 和當前 sIdx = i，模式指針前進。後續失配時，回溯到星號位置，將 '*' 匹配更多字符（sIdx++）。

Java 參考實現

public boolean isMatch(String s, String p) {
    int i = 0, j = 0, starIdx = -1, sIdx = -1;
    while (i < s.length()) {
        if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            i++; j++; // 字符匹配
        } else if (j < p.length() && p.charAt(j) == '*') {
            starIdx = j; sIdx = i; j++; // 記錄星號位置
        } else if (starIdx != -1) {
            j = starIdx + 1; // 回溯：星號匹配更多字符
            i = ++sIdx;
        } else return false; // 無星號可回溯，匹配失敗
    }
    // 跳過尾部多餘星號
    while (j < p.length() && p.charAt(j) == '*') j++;
    return j == p.length();
}

關鍵點解析

• starIdx 記錄最後一個 '*' 在模式中的位置
• sIdx 記錄該星號當前匹配到的字符串位置
• 失配時回溯：模式指針回到星號後一位，字符串指針推進一位（星號吸收更多字符）
• 時間 O(m+n)，空間 O(1)，優於 DP 的 O(mn)

測試用例驗證

isMatch("aa", "a") → false
isMatch("aa", "*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false