做题链接：字符串通配符__牛客网 (nowcoder.com)
要求：实现如下2个通配符(不区分大小写)：
* ：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？ ：匹配1个字符
输入：通配符表达式；一组字符串。
输出：返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：1≤s≤100 1\le s\le 100\ 1≤s≤100
示例：
pq pppq |
false |
**Z 0QZz |
true |
?*Bc*? abcd |
true |
h*?*a h#a |
false |
p*p*qp**pq*p**p***ppq pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp |
false |
做题思路 ： dp 问题 使用二维数组解决问题
假设两个字符串分别是 ABCD * BC * ? ，那么我们就可以画出如下图
1. 为什么多一行为 null? ----> 因为字符串可能为空 其实这就是一点一点匹配的过程
2. 先填充为 null 的部分
3. 匹配剩余地方
我们可以根据 横轴的字母来分类判断是否为 T
* ：左边 || 上面 || 左上角
? : 当前位置可以匹配 且左上角为 T 就为 T
字母/数字：当前位置可以匹配，左上角 为 T 就为 T
得到下图 ，我们可以看到最后一个 为 T 那么也就代表 这两个字符串可以匹配。
最终代码：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Scanner scanner = new Scanner(System.in); String str1 = scanner.nextLine().toLowerCase();//带通配符的字符串 String str2 = scanner.nextLine().toLowerCase();//不带通配符的字符串 boolean ret = isMatching(str1, str2); System.out.println(ret); } public static boolean isMatching(String s1, String s2) { boolean[][] arr = new boolean[s2.length() + 1][s1.length() + 1]; //我们使用 0 代表 false 1 代表 true //1.首先把第一行和第一列搞定 // 第一行： arr[0][0] = true; for (int i = 1; i <= s1.length(); i++) { char ch = s1.charAt(i - 1); if (ch == '*') { arr[0][i] = arr[0][i - 1]; } else { arr[0][i] = false; } } // 第一列 for (int i = 1; i <= s2.length(); i++) { char ch = s2.charAt(i - 1); if (ch == '*') { arr[i][0] = arr[i - 1][0]; } else { arr[i][0] = false; } } //2.填充其他部分 for (int i = 1; i <= s2.length(); i++) { for (int j = 1; j <= s1.length(); j++) { char ch = s1.charAt(j - 1); //①判断是*的情况 if (ch == '*' && isOk(s2.charAt(i - 1))){ arr[i][j] = arr[i - 1][j] || arr[i][j - 1] || arr[i-1][j-1]; } //②判断是 ? 的情况 else if (ch == '?' && isOk(s2.charAt(i - 1))) { arr[i][j] = arr[i - 1][j - 1]; } //③不是通配符的情况 else{ if (ch == s2.charAt(i - 1) && arr[i - 1][j - 1]) { arr[i][j] = true; } else { arr[i][j] = false; } } } } return arr[s2.length()][s1.length()]; } public static boolean isOk(char ch) { return ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9' || ch >= 'A' && ch <= 'Z'; } }
