牛客出bug（华为机试HJ71）

华为机试HJ71）"/>

牛客出bug（华为机试HJ71）

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];// 初始化dpfor (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;}}// 常规dpfor (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;}}// 常规dpfor (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.