题解 | 字符串通配符

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String p = in.nextLine();
        System.out.println(isMatch(s, p) ? "true" : "false");
    }

    private static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            if (s.charAt(i - 1) == '*' && dp[i - 1][0]) {
                dp[i][0] = true;
            } else {
                dp[i][0] = false;
            }
        }

        for (int i = 1; i <= m; i++) {
            char sc = s.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                if (sc == '*') {
                    boolean case0 = dp[i - 1][j];
                    boolean caseMore = isAlphanumeric(pc) && dp[i][j - 1];
                    dp[i][j] = case0 || caseMore;
                } else if (sc == '?') {
                    dp[i][j] = isAlphanumeric(pc) && dp[i - 1][j - 1];
                } else {
                    dp[i][j] = charMatch(sc, pc) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    private static boolean isAlphanumeric(char c) {
        return Character.isLetterOrDigit(c);
    }

    private static boolean charMatch(char a, char b) {
        if (Character.isLetter(a)) {
            return Character.toLowerCase(a) == Character.toLowerCase(b);
        } else {
            return a == b;
        }
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 初始化动态规划数组：dp[0][0] 初始化为 true，表示空字符串匹配空模式。
2. 处理边界条件：当目标字符串为空时，只有通配符字符串全为 '*' 时才可能匹配。
3. 状态转移：'*' 处理：可以匹配零个或多个字符。匹配零个字符时继承前一个状态；匹配多个字符时检查当前字符是否为字母或数字。'?' 处理：检查当前字符是否为字母或数字，并继承前一个状态。普通字符处理：检查字符是否匹配（考虑大小写）。