题解 | 通配符匹配

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param p string字符串 
     * @return bool布尔型
     */
    bool isMatch(string s, string p) {
        // write code here
        int n = s.size(), m = p.size();
        int i = 0, j = 0;     // i指向s，j指向p
        int start = -1;        // 最近一次出现'*'的位置
        int match = 0;        // 当star记录时，s中匹配开始的位置

        while (i < n) {
            if (j < m && (p[j] == '?' || p[j] == s[i])) {
                // 当前字符可匹配：普通相等或'?'
                ++i; ++j;
            } else if (j < m && p[j] == '*') {
                // 记录星号，并先让它匹配空串
                start = j;
                match = i;
                ++j;
            } else if (start != -1) {
                // 之前有'*'，回溯：让'*'多吃一个字符
                j = start + 1;
                ++match;
                i = match;
            } else {
                return false; // 无法匹配且没有可回溯的'*'
            }
        }

        // p剩下的必须全是'*'
        while (j < m && p[j] == '*') ++j;
        return j == m;
    }
};