题解 | #字符串通配符#
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
import java.util.*;
import java.io.*;
// 三种方法，递归、正则表达、动态规划，
//注意到我简化了第一个字符串，因为*和多个*作用相同，简化后很多超时用例就能跑通了
publicclassMain {
publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);
Stringvalue;
while (sc.hasNextLine()) {
value = sc.nextLine();
Stringtarget = sc.nextLine();
value = value.toLowerCase();
target = target.toLowerCase();
// System.out.println(matchStr(value,target));
//简化一下，*和********其实没区别，但是在计算中容易超时间、空间
Stringsimpled_value = value.replaceAll("\\*{2,}","\\*");
// System.out.println(compareChar(simpled_value,target,0,0));
System.out.println(isMatch(simpled_value,target));
}
}
publicstaticbooleancompareChar(Strings1,Strings2,intp1,intp2){
if(p1 == s1.length() && p2 ==s2.length()){
returntrue; //在上一次递归中，p1、p2分别指向s1、s2的末尾，
//并且p1指向一个‘？’或‘*’，或者p1p2
//所指向的字符相同，p1p2分别加1，才有可能结果为true，而只要有一个true
//之前所有的递归结果都是true
}
elseif(p1 == s1.length() || p2 == s2.length()){
returnfalse;//else p1、p2并不是在上一次的递归中都是指向末尾，
//而是只有一个指向了末尾，那么
//这样的递归结果就是false，因为之后缺失了，
//长短不一样,不用比较也知道不匹配了。
}
//假如读取到了*，说明可能匹配0到无穷多个字符，那么就有两种处理方式，一种是继续匹配s2的下一个字符,可以理解为*匹配了无穷多个字符；
//一种是s1、s2都进一步匹配，可以理解为*匹配了一个字符
if(s1.charAt(p1)=='*'){
if(p1==s1.length()-1&&p2==s2.length()-1){
returncompareChar(s1,s2,p1+1,p2+1);
}
returncompareChar(s1,s2,p1,p2+1) || compareChar(s1,s2,p1+1,p2);
}
//假如读取到了？，说明只能匹配一个字符，那就只能都继续进一步匹配了，因为不存在匹配多位的情况
elseif(s1.charAt(p1)=='?'){
if(Character.isLetterOrDigit(s2.charAt(p2))){
returncompareChar(s1,s2,p1+1,p2+1);
}
//?无法匹配非数字字母字符，故return false
else{
returnfalse;
}
}
//不是通配符，那么就是字符，数字字符特殊符号都有可能，但是相同，那么就跳过
elseif(s1.charAt(p1)==s2.charAt(p2)){
returncompareChar(s1,s2,p1+1,p2+1);
}
//不相同，那么匹配失败
else {
returnfalse;
}
}
//本题实际就是异化的正则化，将*？的功能用正则化实现即可
publicstaticbooleanmatchStr(Strings1,Strings2){
Stringregx = s1.replaceAll("\\*{2,}","\\*");
regx = regx.replaceAll("\\?","[0-9a-z]{1}");
regx = regx.replaceAll("\\*","[0-9a-z]{0,}");
returns2.matches(regx);
}
//动态规划核心要点：画一个表格，第一行第一列是边界条件，需要在正式计算前填好，
//例如本题中的第一个for循环
//这个二维的数组（表格），每个格子(i,j)中的boolean值表示第一个字符串从0到i，与第二个字符串从
//0到j的子串的匹配情况(true or false)，boolean 默认false，然后通过子字符串与当前字符串的关联
//依次将其余格子填好，最终结果是格子最右下角的那个值
publicstaticbooleanisMatch(Strings1,Strings2){
char[] chars1 = s1.toCharArray();
char[] chars2 = s2.toCharArray();
boolean[][] dp = newboolean[chars1.length+1][chars2.length+1];
dp[0][0] = true; //两个子字符串都是空显然是匹配的，0=0
//因为*可以匹配0个字符，所以第一个字符串是以*或者多个连续的*开头，那么他们都是true
for(inti=1;i<chars1.length+1;i++){
if(chars1[i-1]=='*'){
dp[i][0]=true;
}elsebreak;
}
for(inti=1;i<=chars1.length;i++){
for(intj=1;j<=chars2.length;j++){
if(chars1[i-1]==chars2[j-1]){
dp[i][j]=dp[i-1][j-1]; //假如字符相同，可以“消去”这个字符串，然后再比较
//消去之后的匹配结果
}
if(chars1[i-1]=='?'&&Character.isLetterOrDigit(chars2[j-1])){
dp[i][j]=dp[i-1][j-1]; //假如是?且要匹配的是字母或数字(因为无法匹配其他字符)
//同样可以视为"消去"之后比较匹配结果
}
elseif(chars1[i-1]=='*'&&Character.isLetterOrDigit(chars2[j-1])){
//第一个理解为*匹配0个字符，相当于没有
//第二个理解为匹配多个字符
//最后一个好理解，*本来就有？的功能
dp[i][j]=dp[i-1][j]|dp[i][j-1]|dp[i-1][j-1];
}
}
}
return dp[chars1.length][chars2.length];
}
}
