题解 | #字符串通配符#

import java.util.*;

/**
 * 动态规划
 * 思路：我们先不考虑 * 的存在。假如没有 * 的话，我们判断两个字符串是否匹配就非常简单，
 * 即 s 和 t 是否匹配当且仅当 s 的每一个字符和 t 对应位置字符是否可以匹配即可，之后
 * 再考虑加入 * 的情况，因为 * 的存在，导致其可以有不确定的情况，即匹配 0 || 1 || 多
 * 个字符，因此这就导致我们需要进行动态规划了。
 * 我们定义 dp[i][j] 为 s 的前 i 个字符和 t 的前 j 个字符是否可以匹配，
 * 其中状态转移方程为
 * 当 t 的第 j 个字符为 * 时：dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i-1][j-1]
 *                                      0 个            多个          1 个
 * 当 t 的第 j 个字符不为 * ,且这两个对应字符可以匹配时：dp[i][j] = dp[i-1][j-1]
 * 原始初始化dp[0][0] = true , 其余均为 false
 * 根据错误改进后的初始化:初始化dp[0][0] = true,
 * 且若当 t 的第 j 个字符为 * 时 dp[0][j] = dp[0][j-1],其余均为 false
 * 最终返回dp[sLen][tLen]即可
 *
 * 程序错误：（需要加入初始化中）
 * 可是这样子写出来的程序有一种情况无法处理，就是当 t 字符串开头为 * 时，
 * 比如 t:*h s:h 按理来说是可以匹配的，但是当我们判断到 s 的第1个字符
 * 和 s 的2个字符相等的时候，我们执行的是 dp[i][j] = dp[i-1][j-1]，
 * 而 dp[0][1] = false ，导致最终结果为 false，及我们需要先对dp的
 * 第 0 行处理一下。
 * 这个处理的实际含义就是当 t 中第一个为 * ，或者从开始一直为 * 的时候，
 * 尽管 s 没有字符，也是可以匹配的，因为 * 可以匹配 0 个字符。
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //匹配时不区分大小写,全转化为小写，方便处理
        String t = scanner.nextLine().toLowerCase();
        String s = scanner.nextLine().toLowerCase();
        int tLen = t.length();
        int sLen = s.length();
        boolean[][] dp = new boolean[sLen + 1][tLen + 1];
        //初始化
        dp[0][0] = true;
        //初始化第一行
        for (int i = 1; i < tLen + 1; i++) {
            if (t.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 1];
            }
        }
        //状态转移
        for (int i = 1; i < sLen + 1; i++) {
            for (int j = 1; j < tLen + 1; j++) {
                if (t.charAt(j - 1) == '*') {
                    //可以匹配
                    if (canMatch(s.charAt(i - 1))) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
                    }
                    //不可以匹配就为false
                } else {
                    if (t.charAt(j - 1) == '?' && canMatch(s.charAt(i - 1))) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        System.out.println(dp[sLen][tLen]);
    }

    private static Boolean canMatch(char ch) {
        return (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z');
    }
}