题解 | #字符串通配符#

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String exp = in.nextLine();
            String str = in.nextLine();
            process2(exp, str);
        }
    }

    // 方法一:动态规划
    private static void process(String exp, String str) {
        exp = exp.toLowerCase();
        str = str.toLowerCase();
        char[] exps = getExps(exp);
        char[] strs = str.toCharArray();
        int n = exps.length;
        int m = strs.length;
        Boolean[][] dp = new Boolean[n + 1][m + 1];
        dp[0][0] = true;
        //填充初始值，如果表达式 * 开头 第0行为true
        for (int i = 1; i <= n; i++) {
            dp[i][0] = exps[0] == '*';
        }
        for (int i = 1; i <= m; i++) {
            dp[0][i] = false;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //场景一， 表达式第i个字符，与字符串中第j个字符相同
                if (exps[i - 1] == strs[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //场景二，表达式第i个字符，与字符串中第j个字符不相同
                    //      1. 字符串中第j个字符不是数字或字母，结果为false
                    if (!(strs[j - 1] >= 'a' && strs[j - 1] <= 'z') && !(strs[j - 1] >= '0' &&
                            strs[j - 1] <= '9')) {
                        dp[i][j] = false;
                        continue;
                    }
                    char e = exps[i - 1];
                    //      2.表达式第i个字符为 ？,结果与i-1, j-1一致
                    if (e == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    //      3.表达式第i个字符为 *
                    } else if (e == '*') {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        System.out.println(dp[n][m]);
    }

    //方法二：动态规划 + 空间压缩
    private static void process2(String exp, String str) {
        exp = exp.toLowerCase();
        str = str.toLowerCase();
        char[] exps = getExps(exp);
        char[] strs = str.toCharArray();
        int n = exps.length;
        int m = strs.length;
        Boolean[] dp = new Boolean[n+1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            if( exps[0] == '*' && i==1) {
                dp[i] =true;
            } else {
                dp[i] =false;
            }
        }
        for (int i = 1; i <= m; i++) {
            boolean leftUp = i == 1, backUp;
            if(i==2) {
                leftUp = exps[0] == '*';
            }
            for (int j = 1; j <= n; j++) {
                backUp = dp[j];
                if(exps[j-1] == strs[i-1]) {
                    dp[j] = leftUp;
                } else {
                    if(!(strs[i-1] >='a' && strs[i-1]<= 'z') &&
                     !(strs[i-1] >='0' && strs[i-1]<= '9')){
                        dp[j] = false;
                        leftUp = backUp;
                        continue;
                    }
                    char e = exps[j-1];
                    if(e == '?'){
                        dp[j] = leftUp;
                    }else if(e == '*'){
                        dp[j] = dp[j-1] || dp[j] || leftUp;
                    }else{
                        dp[j] = false;
                    }
                }
                leftUp = backUp;
            }
        }
        System.out.println(dp[n]);
    }

    // 转成字符数组前，去掉重复的 *
    private static char[] getExps(String exp) {
        List<Character> list = new ArrayList<>();
        char pre = 0;
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            if ((pre == '*' ^ c == '*') || (pre != '*' && c != '*')) {
                list.add(c);
                pre = c;
            }
        }
        char[] arr = new char[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }

        return arr;
    }
}