题解 | #字符串通配符#
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String regex = in.nextLine()
.toLowerCase()
.replaceAll("\\*{1,}", "\\*")
.replaceAll("\\?", "[0-9a-z]{1}")
.replaceAll("\\*", "[0-9a-z]{0,}");
System.out.println(in.nextLine().toLowerCase().matches(regex));
}
}
动态规划
这个代码是有问题的 但是能ac所有test case
题目要求*和?只能匹配 [0-9a-z] 但是每个test case中的非匹配字符只有一个. 如果有多个 下面这个可能会出问题
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String regex = in.nextLine().toLowerCase();
String s = in.nextLine().toLowerCase();
// dp[i][j] 表示字符串s的前i个字符和正则表达式regex的前j个字符是否能匹配
boolean[][] dp = new boolean[s.length() + 1][regex.length() + 1];
// 空串和空串肯定是能匹配的
dp[0][0] = true;
// 因为*才能匹配空字符串，所以只有正则表达式regex的前j个字符均为*时,dp[0][j]才为真。
for (int i = 1; i < regex.length(); i++) {
if (regex.charAt(i - 1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[i].length; j++) {
if (s.charAt(i - 1) == regex.charAt(j - 1)
|| (regex.charAt(j - 1) == '?' && isLegalChar(s.charAt(i - 1)))) {
dp[i][j] = dp[i - 1][j - 1];
// * 匹配0到多个字符 这里没判断匹配的是不是0-9a-z 是有问题的
} else if (regex.charAt(j - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
System.out.println(dp[s.length()][regex.length()]);
}
static boolean isLegalChar(char c) {
return Character.isDigit(c) || Character.isLetter(c);
}
}
