题解 | #字符串通配符#

1. 先将目标串s中的大写字母转化为小写字母
2. 定义动态规划方程意义，dp[i][j]表示表示p(包含*?的模式串)的前i个字符是否能与s的前j个字符匹配

• 定义动态规划方程的边界

• 找出动态规划方程递推公式

import java.util.*;

// 注意类名必须为 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 p = in.nextLine();
            String s = in.nextLine();
            // 检验s中是否存在除字母和数字以外的字符
            char[] arr_s = s.toCharArray();
            for(int i=0;i<arr_s.length;i++){
                char c = arr_s[i];
                if(Character.isUpperCase(c)) arr_s[i] = Character.toLowerCase(c);
            }
            s = String.valueOf(arr_s);
            System.out.println(isMatch(p, s));
        }
    }
    
    public static boolean isMatch(String p, String s){
        int m = p.length(), n = s.length();
        // dp[i][j]表示p的前i个字符是否能与s的前j个字符匹配
        boolean[][] dp = new boolean[m+1][n+1];
        // 初始化边界
        dp[0][0] = true; // 空字符串可以匹配
        for(int i=1;i<=m;i++){
            if(p.charAt(i-1) == '*'){  // *可以匹配0个任意字符，当p的前面连续为*时，可以表示为不存在
                dp[i][0] = true;
            }else{
                break;
            }
        }
        for(int i=1;i<=m;i++){
            char pc = p.charAt(i-1);
            if(Character.isUpperCase(pc)) pc = Character.toLowerCase(pc);
            for(int j=1;j<=n;j++){
                char sc = s.charAt(j-1);
                if(pc == sc || (pc == '?' && (Character.isDigit(sc) || Character.isLetter(sc)))){ //当前字符与s中第j个字符相同
                    dp[i][j] = dp[i-1][j-1];
                }else if(pc == '*'){
                    // 不使用'*',或 使用‘*’
                    // dp[i][j-1]是由 dp[i][0] || dp[i][1] ||... || dp[i][j-1]而来的， 而dp[i][j-2] 又是由dp[i][0] || ... ||dp[i][j-2]而来的， 所以此处直接可以由dp[i][j-1]递推而来
                    /*  该循环与下面的dp[i][j] = dp[i-1][j] || dp[i][j-1]是等价的，只不过使用该循环易于理解
                    for(int k=0;k<j;k++){
                        dp[i][j] = dp[i-1][j] || dp[i][k];
                    }*/
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }else{
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
    
}