题目
问题描述:
在计算机中,通配符一种特殊语法,广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求:
实现如下2个通配符:
- *:匹配0个或以上的字符(注:能被*和?匹配的字符仅由英文字母和数字0到9组成,下同)
- ?:匹配1个字符
注意:匹配时不区分大小写。
输入:
通配符表达式;
一组字符串。
输出:
返回不区分大小写的匹配结果,匹配成功输出true,匹配失败输出false。
数据范围:字符串长度:1≤s≤100。
进阶:时间复杂度:O(n^2),空间复杂度:O(n)。
输入描述:
先输入一个带有通配符的字符串,再输入一个需要匹配的字符串。
输出描述:
返回不区分大小写的匹配结果,匹配成功输出true,匹配失败输出false。
示例1
输入:
te?t*.*
txt12.xls
输出:
false文章来源:https://www.toymoban.com/news/detail-618211.html
示例2
输入:
z
zz
输出:
false
示例3
输入:
pq
pppq
输出:
false
示例4
输入:
**Z
0QZz
输出:
true
示例5
输入:
?*Bc*?
abcd
输出:
true
示例6
输入:
h*?*a
h#a
输出:
false
说明:根据题目描述可知能被*和?匹配的字符仅由英文字母和数字0到9组成,所以?不能匹配#,故输出false
示例7
输入:
p*p*qp**pq*p**p***ppq
pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp
输出:
false
代码文章来源地址https://www.toymoban.com/news/detail-618211.html
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()) {
String t = sc.nextLine();
String s = sc.nextLine();
System.out.println(match(t, s));
}
}
public static boolean match(String t, String s) {
char[] ct = t.toCharArray();
char[] cs = s.toCharArray();
int lt = ct.length;
int ls = cs.length;
boolean[][] dp = new boolean[ls + 1][lt + 1];
dp[0][0] = true;
for(int i = 0; i <= ls; i++) {
for(int j = 1; j <= lt; j++) {
if(ct[j - 1] == '*') {
if(i == 0) {
dp[i][j] = dp[i][j - 1];
} else {
if(cs[i- 1] == '.' || (cs[i - 1] == 'A' && cs[i - 1] <= 'Z') || (cs[i - 1] >= 'a' && cs[i - 1] <= 'z') || (cs[i - 1] >= '0' && cs[i - 1] <= '9')) {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
} else {
if(i > 0 && defs(ct[j - 1], cs[i - 1])) {
dp[i][j] = dp[i- 1][j - 1];
}
}
}
}
return dp[ls][lt];
}
public static boolean defs(char t, char s) {
if(t == '?') {
return true;
}
if(t >= 'a' && t <= 'z') {
t = (char)(t - 'a' + 'A');
}
if(s >= 'a' && s <= 'z') {
s = (char)(s - 'a' + 'A');
}
return s == t;
}
}
到了这里,关于16-字符串通配符的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!