题解 | #字符串通配符#

• 使用动态规划解决
• d[i][j]表示模式t[0:i]与字符串s[0:j]是否能够匹配
• 当t[i]='*'时，如果t[0:i-1]与s[0:j]匹配或者t[0:i]和s[0:j-1]匹配则必有t[0:i]与字符串s[0:j]匹配
• 当t[i]与s[j]字符匹配时，并且t[0:i-1]与s[0:j-1]匹配，则必有t[0:i]与字符串s[0:j]匹配
• 综上所述可以得到递推式
• 另外求解动态规划的边界条件

/**
 动态规划
 dp[i][j] 表示t[i] s[j]是不是能够匹配到
 dp[0][0] 看下t[0] s[0]能不能匹配到
 dp[i][j] = dp[i][j-1] || dp[i-1][j] ,如果t[i]='*' || dp[i-1][j-1],如果t[i],s[j]能够匹配 || dp[i-1][j] 如果t[i]==*
*/

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String t = sc.nextLine();
            String s = sc.nextLine();
            System.out.println(match(t,s));
        }
    }
    
    
    public static boolean match(String t, String s){
        int lt = t.length(), ls = s.length();
        boolean[][] dp = new boolean[lt][ls];
        //确定动态规划的边界
        //dp[0][i];
        for(int i = 0; i < ls; i++){
            if(i == 0){
                dp[0][0] = matchChar(t.charAt(0),s.charAt(0));
            }else{
                dp[0][i] = dp[0][i-1] && matchChar(t.charAt(0),s.charAt(i)) && t.charAt(0) == '*';
            }
        }
        //dp[i][0]
        boolean allStar = t.charAt(0) == '*';
        for(int i = 1; i < lt; i++){
            dp[i][0] = (dp[i-1][0] && t.charAt(i) == '*') || (allStar && matchChar(t.charAt(i),s.charAt(0)));
            if(t.charAt(i) != '*'){
                allStar = false;
            }
        }
        // 先覆盖t的维度 确定的s，遍历t
        for(int i = 1; i < lt; i++){
            for(int j = 1; j < ls; j++){
                dp[i][j] = (t.charAt(i) == '*' && (dp[i-1][j] || dp[i][j-1])) || (dp[i-1][j-1] && matchChar(t.charAt(i), s.charAt(j)));
            }
        }
        return dp[lt - 1][ls - 1];
    }
    
    public static boolean matchChar(char t, char s){
        if(Character.isLetter(t) && Character.isLetter(s) && (Character.toLowerCase(t) == Character.toLowerCase(s))){
            return true;
        }
        if((t == '*' || t == '?') && (Character.isDigit(s) || Character.isLetter(s))){
            return true;
        }
        //其他字符
        if(t == s){
            return true;
        }
        return false;
    }
}