NC44：通配符匹配

思路1：动态规划

在给定的模式 p 中，只会有三种类型的字符出现：

• 小写字母 a-z，可以匹配对应的一个小写字母；
• 问号 ?，可以匹配任意一个小写字母；
• 星号 *∗，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母
  其中「小写字母」和「问号」的匹配是确定的，而「星号」的匹配是不确定的，因此我们需要枚举所有的匹配情况。为了减少重复枚举，我们可以使用动态规划来解决本题
  
  

  public class Solution {
    public boolean isMatch(String s, String p) {
        int slen=s.length();
        int plen=p.length();
        boolean[][] dp=new boolean[slen+1][plen+1];
        dp[0][0]=true;
        for(int j=1;j<=plen;j++){
            if(p.charAt(j-1)=='*'){
                dp[0][j]=true;
            }
            else{
                break;
            }
        }
        for(int i=1;i<=slen;i++){
            for(int j=1;j<=plen;j++){
                if(p.charAt(j-1)=='*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
                else if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='?'){
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[slen][plen];
    }
  }

复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
• 空间复杂度：O(mn)，即为存储所有 (m+1)(n+1)个状态需要的空间。此外，在状态转移方程中，由于 dp[i][j] 只会从 dp[i][..] 以及 dp[i−1][..] 转移而来，因此我们可以使用滚动数组对空间进行优化，即用两个长度为 n+1的一维数组代替整个二维数组进行状态转移，空间复杂度为 O(n)。

思路2：贪心

本题难点在于处理星号的匹配，用iStar和jStar表示星号在s和p中匹配的位置，初始值为-1，i和j表示当前匹配的位置，匹配过程如下：

• 如果s和p中字符匹配，则分别自增i和j
• 否则如果p中当前字符为星号，则标记iStar和jStar，同时自增j
• 否则如果iStar >= 0，表示之前匹配过星号，因为星号可以匹配任意字符串，所以继续递增i，同时移动j为jStar下一个字符
• 否则返回false
• 当s中字符匹配完，p中字符不能有除星号以外字符

  bool isMatch(string s, string p) {
        int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
        while (i < m) {
            if (j < n && (s[i] == p[j] || p[j] == '?')) {
                ++i, ++j;//i，j向后瞬移
            } else if (j < n && p[j] == '*') {
            //记录如果之后序列匹配不成功时， i和j需要回溯到的位置
                iStar = i;//记录星号，*可以匹配空字符
                jStar = j++;
                //记录星号 并且j移到下一位 准备下个循环s[i]和p[j]的匹配
            } else if (iStar >= 0) {
                //发现字符不匹配且没有星号出现 但是istar>0 说明可能是*匹配的字符数量不对 这时回溯
                i = ++iStar;
                //i回溯到istar+1 因为上次从s串istar开始对*的尝试匹配已经被证明是不成功的（不然不会落入此分支） 
                //所以需要从istar+1再开始试 同时inc istar 更新回溯位置
                j = jStar + 1;
                //j回溯到jstar+1 重新使用p串*后的部分开始对s串istar
                //（这个istar在上一行已经inc过了）位置及之后字符的匹配 
            } else return false;
        }
        while (j < n && p[j] == '*') 
             ++j;//去除多余星号
        return j == n;
    }