题解 | #字符串通配符#

h*h*ah**ha*h**h***hha

hhhhhhhahhaahhahhhhaaahhahhahaaahhahahhhahhhahaaahaah

false

以上测试用例深度优先算法和String的matches方法运行时间都会超过1秒

推荐动态规划算法

import java.util.Scanner;

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

        String s1 = in.nextLine();
        String s2 = in.nextLine();
        while (s1.contains("**")) {
            s1 = s1.replaceAll("\\*\\*", "*");
        }
        // System.out.print(dfs(s1.toLowerCase(), s2.toLowerCase(), 0, 0));
        // System.out.print(getOc(s1.toLowerCase(), s2.toLowerCase()));
        System.out.print(dp(s1.toLowerCase(), s2.toLowerCase()));
    }


// h*h*ah**ha*h**h***hha
// hhhhhhhahhaahhahhhhaaahhahhahaaahhahahhhahhhahaaahaah
// false
//以上测试用例深度优先算法和String的matches方法所用时间都会超过1秒
    private static boolean dfs(String s1, String s2, int p1, int p2) {
        if (s1.length() == p1 && s2.length() == p2) {
            return true;
        } else if (s1.length() == p1 || s2.length() == p2) {
            return false;
        }

        if (s1.charAt(p1) == '*') {
            if (String.valueOf(s2.charAt(p2)).matches("[A-Za-z0-9]")) {
                return dfs(s1, s2, p1 + 1, p2) || dfs(s1, s2, p1, p2 + 1) ||
                       dfs(s1, s2, p1 + 1, p2 + 1);
            } else {
                return dfs(s1, s2, p1 + 1, p2 + 1);
            }
        } else if (s1.charAt(p1) == '?' || s1.charAt(p1) == s2.charAt(p2)) {
            return dfs(s1, s2, p1 + 1, p2 + 1);
        } else {
            return false;
        }

    }

    public static  boolean getOc(String in, String temp) {
        //字符串通配符
        in = in.replaceAll("\\?", "[0-9A-Za-z]{1}");
        in = in.replaceAll("\\*", "[0-9A-Za-z]{0,}");
        //in = in.replaceAll("\\.", "\\\\.");
        return temp.matches(in);
    }

    private static boolean dp(String s1, String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 1; i <= len1; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                char c2 = s2.charAt(j - 1);
                if (c1 == c2 || (c1 == '?' && String.valueOf(c2).matches("[A-Za-z0-9]"))) {
                    dp[i][j] = dp[i - 1][j - 1] || dp[i - 1][j];
                } else if (c1 == '*') {
                    if (String.valueOf(c2).matches("[A-Za-z0-9]")) {
                        dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[len1][len2];
    }
}