题解 | #字符串通配符#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String regex = in.nextLine()
                       .toLowerCase()
                       .replaceAll("\\*{1,}", "\\*")
                       .replaceAll("\\?", "[0-9a-z]{1}")
                       .replaceAll("\\*", "[0-9a-z]{0,}");
        System.out.println(in.nextLine().toLowerCase().matches(regex));
    }
}

动态规划

这个代码是有问题的 但是能ac所有test case

题目要求*和?只能匹配 [0-9a-z] 但是每个test case中的非匹配字符只有一个. 如果有多个 下面这个可能会出问题

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String regex = in.nextLine().toLowerCase();
        String s = in.nextLine().toLowerCase();
        // dp[i][j] 表示字符串s的前i个字符和正则表达式regex的前j个字符是否能匹配
        boolean[][] dp = new boolean[s.length() + 1][regex.length() + 1];
        // 空串和空串肯定是能匹配的
        dp[0][0] = true;
        // 因为*才能匹配空字符串，所以只有正则表达式regex的前j个字符均为*时,dp[0][j]才为真。
        for (int i = 1; i < regex.length(); i++) {
            if (regex.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (s.charAt(i - 1) == regex.charAt(j - 1)
                        || (regex.charAt(j - 1) == '?' && isLegalChar(s.charAt(i - 1)))) {
                    dp[i][j] = dp[i - 1][j - 1];
                // * 匹配0到多个字符 这里没判断匹配的是不是0-9a-z 是有问题的
                } else if (regex.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[s.length()][regex.length()]);
    }

    static boolean isLegalChar(char c) {
        return Character.isDigit(c) || Character.isLetter(c);
    }
}