题解 | #通配符匹配#

这题是p串匹配s串。其中p串含有'?'（能匹配任一个字符），'*'能匹配任意字符串包括空串。 使用动态规划：f[i][j]表示s串前i个字符匹配p串前j个字符的结果。分为三种情况：

• p串第j个字符串既不是'?'，也不是'*'，那么当s串第i个字符与p串第j个字符相同时，f[i][j]取决于f[i-1][j-1]
• p串第j个字符是'?'，那么能匹配s[i]，f[i][j]同样取决于f[i-1][j-1]
• p串第j个字符是'*'
  • 当'*'匹配空串时，f[i][j]取决于f[i][j-1]，这个很直观
  • 当'*'匹配非空串时，f[i][j]取决于f[i-1][j] ，因为此时'*'表示多个字符，需要保持'*'不动，那么s串第i个字符以及后面的字符串f[i~][j]都取决于f[i-1][j]，当f[i-1][j]为true可以匹配时，那么f[i~][j]都为true，都可以匹配。
• 本题还需要注意初始化，即f[0][0]为true，此外当p串前面连续子串都是*时，f[0][j]都是true

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