Hj71：字符串通配符

描述

问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符

注意：匹配时不区分大小写。

输入：
通配符表达式；
一组字符串。

输出：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

数据范围：字符串长度 1≤s≤100 

进阶：时间复杂度：O(n2) ，空间复杂度 O(n) 

输入描述：

先输入一个带有通配符的字符串，再输入一个需要匹配的字符串

输出描述：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

上述为题目，都提示时间复杂度为 O(n2) 了，基本都能想到动态规划吧，废话不多说，先上代码

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String match = in.nextLine();
        String target = in.nextLine();

        System.out.println(dp(match, target) ? "true" : "false");
    }

    /**
     * pass:32/34
     * eg:
     * a*?*c
     * a@c
     * 预计：false！！！！！！！！！！！！！！！todo sotmw???????
     * 实际：true
     * @param match
     * @param target
     * @return
     */
    public static boolean dp(String match, String target) {
        int m = match.length();
        int n = target.length();
        boolean[][] dp = new boolean[m][n];

        // 初始化dp
        for (int j = 0; j < n; ++j) {
            char c = match.charAt(0);
            if (c == '*') {
                dp[0][j] = true;//通配符匹配多个
                if (m > 1) {
                    dp[1][j] = match.charAt(1) == target.charAt(j);//第一位的 * 可能不匹配，多初始化一行
                }
            }
            if (j == 0 && (c == '?' || c == target.charAt(0))) {//dp[0][0] 必须初始化
                dp[0][j] = true;
            }
        }

        // 常规dp
        for (int i = 0; i < m - 1; ++i) {
            for (int j = 0; j < n - 1; ++j) {
                if (dp[i][j]) {
                    char mat = match.charAt(i + 1);
                    if (mat == '*') {
                        for (int j0 = j; j0 < n; ++j0) {
                            dp[i + 1][j0] = true;
                        }
                    } else if (mat == '?') {
                        dp[i + 1][j + 1] = true;
                    } else {
                        dp[i + 1][j + 1] = mat == target.charAt(j + 1);
                    }
                }
            }
        }
        return dp[m - 1][n - 1];
    }

这个用例用眼睛都能匹配，它告诉我说不行！！！！！！！！就问有没有被坑的感觉！！！！！？

===============================分割线===========================

后来我看到了

*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

人为埋雷！！！！！被坑的感觉更强烈了！！！！！！！

搞些杂七杂八的消耗别人的时间精力，完全违背了练习算法的初衷，伤心了

===============================分割线===============================

都写到这个份上了，附上一份完整通过的代码：

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String match = in.nextLine();
        String target = in.nextLine();

        System.out.println(dp(match, target) ? "true" : "false");
    }

    /**
     * pass:32/34
     * eg:
     * a*?*c
     * a@c
     * 预计：false！！！！！！！！！！！！！！！todo sotmw???????
     * 实际：true
     *
     * @param match
     * @param target
     * @return
     */
    public static boolean dp(String match, String target) {
        int m = match.length();
        int n = target.length();
        boolean[][] dp = new boolean[m][n];

        for (int j = 0; j < n; ++j) {
            char c = match.charAt(0);
            if (c == '*') {
                dp[0][j] = true;//通配符匹配多个
                if (m > 1) {
                    dp[1][j] = match(match.charAt(1), target.charAt(j));//第一位的 * 可能不匹配，多初始化一行
                }
            }
            if (j == 0 && match(c, target.charAt(j))) {//dp[0][0] 必须初始化
                dp[0][j] = true;
            }
        }

        // 常规dp
        for (int i = 0; i < m - 1; ++i) {
            for (int j = 0; j < n - 1; ++j) {
                if (dp[i][j]) {
                    char mat = match.charAt(i + 1);
                    if (mat == '*') {
                        for (int j0 = j; j0 < n; ++j0) {
                            dp[i + 1][j0] = checkChar(target.charAt(j0));
                        }
                    } else if (mat == '?') {
                        dp[i + 1][j + 1] = checkChar(target.charAt(j + 1));
                    } else {
                        dp[i + 1][j + 1] = match(mat, target.charAt(j + 1));
                    }
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * （注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
     *
     * @param c
     * @return
     */
    public static boolean checkChar(char c) {
        return 48 <= c && c <= 57 || 65 <= c && c <= 90 || 97 <= c && c <= 122;
    }

    /**
     * 注意：匹配时不区分大小写。
     * 一个注意就要重新抽一个方法封装
     *
     * @param c1
     * @param c2
     * @return
     */
    public static boolean match(char c1, char c2) {
        if (c1 == '*') {
            return checkChar(c2);
        }
        if (c1 == '?') {
            return checkChar(c2);
        }
        int m = c1 - c2;
        if (m != 0) {
            int c11 = c1, c22 = c2;
            if (65 <= c1 && c1 <= 90) {
                c11 = c1 - 64;
            }
            if (97 <= c1 && c1 <= 122) {
                c11 = c1 - 96;
            }
            if (65 <= c2 && c2 <= 90) {
                c22 = c2 - 64;
            }
            if (97 <= c2 && c2 <= 122) {
                c22 = c2 - 96;
            }
            m = c11 - c22;
        }
        return m == 0;
    }

审题远比搬砖重要，下次做华为的题，首先做个 toKengList.