题目描述

题意：给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

’?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

算法1

(动态规划) $O(n*m)$

题解1：和第十题类似，双字符串匹配问题，可以用动态规划来做。

状态表示：dp[i][j]代表s的前i个字符和p的前j个字符是否匹配。

状态初始化：dp[0][0] = true，对于1 <= i <= m如果p[i - 1] = '*' && dp[0][i - 1]那么dp[0][i] = true，这对应着p以***as开头的字符串，因为*可以代表0个字符，所以可以往后匹配。

状态转移：

• s[i - 1] == p[j - 1] || 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][j - 1]

• 如果不是空串，那么dp[i][j] = dp[i - 1][j]。这是因为*代表了任意多个字符，如果能匹配前i - 1个字符，那么就在*代表的字符串后面加上s[i]，就可以匹配前i个字符啦。

C++ 代码

    bool isMatch(string s, string p) {
        int n = s.length(),m = p.length();
        vector<vector<bool>> dp(n + 1,vector<bool> (m + 1,false));
        dp[0][0] = true;
        for(int i = 1 ;i <= m ;i ++)
        {
            if(p[i - 1] == '*' && dp[0][i - 1]) dp[0][i] = true;
            else break;
        }
        for(int i = 1 ; i <= n ; i ++)
        {
            for(int j = 1; j <= m ;j ++)
            {
                if(s[i - 1] == p[j - 1] || p[j - 1] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                    dp[i][j] = dp[i - 1][j] | dp[i][j - 1];
            }
        }
        return dp[n][m];
    }

算法2

(双指针扫描) $O(n*m)$

题解2:双指针扫描。使用i,j分别代表匹配串和模式串当前匹配位置。

• 如果s[i] == p[j] || p[j] == '?'，代表精准匹配，这时候双指针后移
• 如果不能匹配，查看当前是否是*，如果是那么记录当前*号位置，以及当前匹配串指针位置，模式串指针后移。
• 如果不能匹配且不是*，说明这个时候失配了，需要尝试恢复当上一个星号的状态，将模式串指针指向上一个星号的下一个字符，匹配串指针也指向上一次失配的下一个位置，尝试重新匹配。
• 如果不能恢复现场，返回false。

最后去除模式串末尾多余的星号，再判断当字符串匹配完了之后，模式串是否也匹配完了。

最坏的时间复杂度也是$O(n*m)$的，但是平均的时间复杂度会稍微好一点。

C++ 代码

    bool isMatch(string s, string p) {
        int i = 0,j = 0,match = 0,starIdx = -1;
        int n = s.length(),m = p.length();
        while(i < n)
        {
            if(j < m && (s[i] == p[j] || p[j] == '?'))
            {
                i ++;
                j ++;
            }else if(j < m && p[j] == '*')
            {
                starIdx = j;
                match = i;
                j ++;
            }else if(starIdx != -1)
            {
                j = starIdx + 1;
                match ++;
                i = match;
            }
            else
                return false;
        }
        while(j < m && p[j] == '*')
            j ++;
        return j == m;
    }