问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符
输出：
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
te?t*.* txt12.xls
false
z zz
false
pq pppq
false
**Z 0QZz
true
?*Bc*? abcd
true
h*?*a h#a
false
根据题目描述可知能被*和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配#，故输出false
p*p*qp**pq*p**p***ppq pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp
false
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
return a>b?a:b;
}
int match(char a[] ,char b[])
{
int lena = strlen(a);
int lenb = strlen(b);
int dp[100][100] = {0};
dp[0][0] = 1;
for(int j = 0;j < lenb;j++)
{
if((b[j] == '.') || ((b[j] >= '0') && (b[j] <= '9')) || ((b[j] >= 'a') && (b[j] <= 'z')) || ((b[j] >= 'A') && (b[j] <= 'Z')))
{
continue;
}
else
{
return 0;
}
}
for(int i = 1;i <= lena;i++)
{
if(a[i - 1] == '*')
{
dp[i][0] = 1;
}
else
{
break;
}
}
for(int i = 1;i <= lena;i++)
{
for(int j = 1;j <= lenb;j++)
{
if(a[i - 1] == '?')
{
dp[i][j] = max(dp[i][j] , dp[i-1][j-1]);
}
if((a[i - 1] == b[j - 1]) || (a[i - 1] == b[j - 1] + 32) || (a[i - 1] == b[j - 1] - 32))
{
dp[i][j] = max(dp[i][j] , dp[i-1][j-1]);
}
if(a[i - 1] == '*')
{
dp[i][j] = max(dp[i][j] , (dp[i-1][j] || dp[i][j - 1]));
}
}
}
return dp[lena][lenb];
}
int main()
{
int m;
char a[100],b[100];
while(scanf("%s",&a) != EOF)
{
scanf("%s",&b) ;
m = match(a, b);
if(m == 1)
{
printf("true\n");
}
else{
printf("false\n");
}
}
} 
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String value;
while ((value = bf.readLine()) != null) {
String target = bf.readLine();
value = value.toLowerCase(Locale.ROOT);
target = target.toLowerCase(Locale.ROOT);
String regx = value.replaceAll("\\*{2,}","\\*");
regx = regx.replaceAll("\\?","[0-9a-z]{1}");
regx = regx.replaceAll("\\*","[0-9a-z]{0,}");
System.out.println(target.matches(regx));
}
}
}
import re
while True:
try:
string1 = input().lower()
string2 = input().lower()
string1 = string1.replace('?', '[a-z0-9]').replace('.', '\.').replace('*', '[0-9a-z]*')
stringRegex = re.compile(string1)
if stringRegex.search(string2) and string2 == stringRegex.search(string2).group():
print('true')
else:
print('false')
except:
break 
#include <iostream>
using namespace std;
// 一方面将字符全改为小写，另一方面检查字符合法性
bool big2small(string& s)
{
for(char& ch : s)
{
if(ch >= 'A' && ch <= 'Z') ch = ch - ('A' - 'a');
else if(ch >= 'a' && ch <= 'z') continue;
else if(ch >= '0' && ch <= '9') continue;
else if(ch == '*' || ch == '?' || ch == '.') continue;
else
{
return false;
}
}
return true;
}
bool dfs(string& s1, string& s2, int i, int j)
{
if(i == s1.size() && j == s2.size()) return true;
else if(i == s1.size() || j == s2.size()) return false;
if(s1[i] == s2[j] || s1[i] == '?')
return dfs(s1, s2, i + 1, j + 1);
else if(s1[i] != '*') return false;
else
{
// *最少能代替0个字符，最多能代替sz-j个字符
for(int t = 0; t <= s2.size() - j; t++)
{
// 其中有一个情况能成功，则返回true
if(dfs(s1, s2, i + 1, j + t)) return true;
}
return false;
}
}
int main()
{
string s1, s2;
while(cin >> s1 >> s2)
{
// 检查在出现*号之前以及所有*出现完毕之后，有无不匹配字符，也就相当于无*情况
bool finish = false;
// 改小写，检查合法性
if(!(big2small(s1) && big2small(s2)))
{
finish = true;
cout << "false" << endl;
}
// 剪枝，先把*不参与部分比对好
if(!finish)
{
for (int i = 0; s1[i] != '*' && i < s1.size(); i++)
{
if (s1[i] == s2[i] || s1[i] == '?') continue;
else
{
finish = true;
cout << "false" << endl;
break;
}
}
}
if(!finish)
{
int i = s1.size() - 1, j = s2.size() - 1;
while(s1[i] != '*' && i >= 0)
{
if(s1[i] == s2[j] || s1[i] == '?')
{
i--;
j--;
}
else
{
finish = true;
cout << "false" << endl;
break;
}
}
}
if(!finish)
{
// 这里应该只对比*参与的中间部分就够了，懒得写了
if(dfs(s1, s2, 0, 0)) cout << "true" << endl;
else cout << "false" << endl;
}
}
return 0;
}
import java.util.*;
public class Main{
public static void main(String []args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String key = in.next();
String str = in.next();
int num = 0;
boolean flag = true;
for(int i = 0; i < str.length(); i++){
if(key.charAt(num) != '?' && key.charAt(num) != '*' &&key.charAt(num) != str.charAt(i)){
flag = false;
break;
}
if(key.charAt(num) == str.charAt(i) || key.charAt(num) == '?'){
num++;
continue;
}
if(num + 1 < str.length() && i + 1 < str.length()){
if(key.charAt(num + 1) == str.charAt(i + 1)){
num++;
continue;
}
}
if(key.charAt(num) == '*')
continue;
}
System.out.println(flag);
}
in.close();
}
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){
String wildcard = scanner.next();
String target = scanner.next();
System.out.println(matchStr(wildcard, target));
}
}
public static boolean matchStr(String wildcard, String target){
int targetIndex = 0;
boolean startFound = false;
for (int i = 0; i < wildcard.length(); i++){
if (startFound){
if ((target.charAt(targetIndex) >= '0' && target.charAt(targetIndex) <= '9') || (target.charAt(targetIndex) >= 'a' && target.charAt(targetIndex) <= 'z') || (target.charAt(targetIndex) >= 'A' && target.charAt(targetIndex) <= 'Z')){
}else{
if (wildcard.charAt(i) != target.charAt(targetIndex)){
return false;
}
startFound = false;
}
}
if (wildcard.charAt(i) == '?'){
}else if (wildcard.charAt(i) == '*'){
startFound = true;
}else{
if (wildcard.charAt(i) != target.charAt(targetIndex)){
return false;
}
}
targetIndex += 1;
}
return true;
}
} 
def match(s1, s2):
# 创建 dp 数组
dp = [[0]*(len(s1) + 1) for _ in range(len(s2) + 1)]
# 初始化 dp 数组
for i in range(len(s2) + 1):
if i == 0:
dp[i][0] = 1
else:
dp[i][0] = 1 if dp[i - 1][0] and s2[i - 1] == '*' else 0
# 状态转移求解 dp 数组
for i in range(1, len(s2) + 1):
for j in range(1, len(s1) + 1):
if s2[i - 1] == '*':
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
else:
dp[i][j] = 1 if dp[i - 1][j - 1] and (s2[i - 1] == '?'&nbs***bsp;s2[i - 1] == s1[j - 1]) else 0
# 返还匹配结果
return dp[-1][-1]
while True:
try:
s2 = input()
s1 = input()
print('true' if match(s1, s2) else 'false')
except:
break 
def error_index(string):
# 输出非法字符的位置
ans = []
for i in range(len(string)):
c = string[i]
if c.isalpha() or c.isnumeric() or c=='*' or c=='?':
continue
else:
ans.append(i)
return ans
def split_by_index(string, index):
# 通过非法符号的位置进行划分
ans = []
index.insert(0, -1)
index.append(len(string))
lengh = len(index)
for i in range(lengh-1):
temp = string[index[i]+1: index[i+1]]
if temp!='':
ans.append(temp)
return ans
def error_cmp(str1,str2,index1,index2):
# 比较非法字符是否一样
for i,j in zip(index1, index2):
if str1[i]!=str2[i]:
return False
return True
def eq(str1, str2):
# 比较通配符 str2是纯字母数字
len1, len2 = len(str1), len(str2)
if len1!=len2 and '*' not in str1:
return False
matrix = [[False for j in range(len2)] for i in range(len1)]
if str1[0]=='*' or str1[0]=='?': matrix[0][0] = True
else:
if str1[0]==str2[0]: matrix[0][0] = True
for i in range(1, len1):
if str1[i]=='*' and matrix[i-1][0]:
matrix[i][0] = True
else:
matrix[i][0] = False
# 重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点
for i in range(1, len1):
for j in range(1, len2):
if str1[i]=='*':
matrix[i][j] = matrix[i-1][j] or matrix[i][j-1]
else:
matrix[i][j] = matrix[i-1][j-1] and (str1[i]=='?'&nbs***bsp;str1[i]==str2[j])
return matrix[len1-1][len2-1]
while True:
try:
error = 0
expression, todo = input(), input()
exp_index, todo_index = error_index(expression), error_index(todo)
if len(exp_index)!= len(todo_index) or not error_cmp(expression, todo, exp_index, todo_index):
error = 1
break
exp_split, todo_split = split_by_index(expression, exp_index), split_by_index(todo, todo_index)
for str1,str2 in zip(exp_split, todo_split):
if not eq(str1, str2):
error = 1
break
if error:
print('false')
else:
print('true')
except:
break 
#include <iostream>
(720)#include <string>
using namespace std;
int main() {
string str1;
string str2;
while (cin >> str1 >> str2) {
int res = 1;
int i = 0;
int flag = 0;
for (auto c : str2) {
if (flag && c == str1[i]) {
flag = 0;
}
if (str1[i] == '*') {
flag = 1;
}
if (c != str1[i] && str1[i] != '?' && !flag) {
res = 0;
}
i++;
}
if (res)
cout << "true" << endl;
else
cout << "false" << endl;
}
} 
#include <bits/stdc++.h>
using namespace std;
int main()
{ string s1,s2; while(cin>>s1>>s2) { int l1=s1.length(),l2=s2.length(); vector<vector<int>> dp(l1+1, vector<int>(l2+1,0)); dp[0][0] = 1; for(int i=1;i<=l1;i++) { char c1 = s1[i-1]; dp[i][0] = dp[i-1][0] && (c1=='*'); for(int j=1;j<=l2;j++) { char c2 = s2[j-1]; if(c1=='*') dp[i][j] = dp[i-1][j] || dp[i][j-1]; else dp[i][j] = dp[i-1][j-1] && (c1=='?' || c1==c2); } } cout<<((dp[l1][l2]==true)?"true":"false")<<endl; } return 0;
}
//不用正则表达式的算法:但是a*bc匹配abc失败
#include <string>
#include <iostream>
using namespace std;
bool isMatched(string s1,string s2);
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
if(isMatched(s1,s2)) cout<<"true"<<endl;
else cout<<"false"<<endl;
}
}
bool isMatched(string s1,string s2)//s1模式串，s2目标串
{
unsigned i=0,j=0;//i是s1的指针，j是s2的指针
for(;i<s1.size()&&j<s2.size();)
{
if(s1[i]=='?')//当前位置匹配
{
i++;j++;
}
else if(s1[i]=='*')
{
if(i==s1.size()-1) return true;//如果当前i是s1最后一个，肯定是匹配的；
if(s1[i+1]!='?')//如果i+1位置不是？，比如3*e匹配3wece,那么在s2中找到第一个不等于s1[i+1]即'e'的位置j
while(s2[j+1]!=s1[i+1]&&j+1<s2.size())
j++;
else//如果i+1位置是？，比如3*?e匹配3wece,那么在s2中找到第一个不等于s1[i+2]即'e'的位置j
while(s2[j+1]!=s1[i+2]&&j+1<s2.size())
j++;
//如果i不是s1的最后一个位置但是s2已经读到最后了，则匹配不成功
if(i<s1.size()-1&&j==s2.size()-1) return false;
//下面两行：如果i+1位置是？，i应前进两位，否则前进一位
if(s1[i+1]=='?') i++;
i++;j++;
}
else
{
if(s1[i]!=s2[j]) return false;
i++;j++;
}
}
return true;//s1扫描结束都没有退出，则匹配成功
} 
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String ptn = sc.nextLine();
String str = sc.nextLine();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < ptn.length(); i++) {
if (ptn.charAt(i) == '?') {
sb.append(".{1}");
} else if (ptn.charAt(i) == '*') {
sb.append(".{0,}");
} else {
sb.append(ptn.charAt(i));
}
}
System.out.println(str.matches(sb.toString()));
}
}
} 
虽然通过了，但是我这个程序有点不足，无法正确的判断a* 与 a是否匹配
import java.util.Scanner;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
String pattern = scan.nextLine();
String target = scan.nextLine();
System.out.println(match(pattern, target, 0, 0));
}
}
public static boolean match(String pattern, String target, int index1,
int index2) {
if (index1 == pattern.length() && index2 == target.length() ) {
return true;
}
if (index1 >= pattern.length() || index2 >= target.length()) {
return false;
}
if (pattern.charAt(index1) == '?') {
return match(pattern, target, index1 + 1, index2 + 1);
} else if (pattern.charAt(index1) == '*') {
// 匹配0个一个或者多个
return match(pattern, target, index1 + 1, index2)
|| match(pattern, target, index1 + 1, index2 + 1)
|| match(pattern, target, index1, index2 + 1);
} else if (pattern.charAt(index1) == target.charAt(index2)) {
return match(pattern, target, index1 + 1, index2 + 1);
}
return false;
}
}
#include<iostream> #include<string> #include<vector> using namespace std; //给一个两个都可以含有通配符的比较方法string s,p; /* 1.s[i] == p[j],且均不等于* dp[i][j] = dp[i-1][j-1]; 2.s[i] != p[j] 且均不等于* 或者？，dp[i][j] = 0; 3.s[i] != p[j],两者其一为普通字符，另外一个为？，dp[i][j] = dp[i-1][j-1]; 4.s[i] != p[j],p[j] ==*,dp[i][j] = (dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||...||dp[1][j-1]); 5.s[i] != p[j],s[i] == * ,dp[i][j] = (dp[i-1][j]||dp[i-1][j-1]||dp[i-1][j-2]||...||dp[i-1][1]); 6.s[i] == p[j] == *,dp[i][j] = (dp[i][j-1]||dp[i-1][j-1]||...dp[1][j-1] ||dp[i-1][j]||dp[i-1][j-1]||dp[i-1][j-2]||...||dp[i-1][1]); */ class Solution { public: bool isMatch(string str1,string str2) { int len1 = str1.length(); int len2 = str2.length(); if (str1 == ""){//特殊情况 if (str2 == "") return true; else { int j = 0; while (j != len2){ if (str2[j] != '*') return false; ++j; } return true; } } if (str2 == ""){//特殊情况 if (str1 == "") return true; else { int i = 0; while (i != len1){ if (str1[i] != '*') return false; ++i; } return true; } } vector<vector<bool> > dp(len1 + 1, vector<bool>(len2 + 1, false)); dp[0][0] = true; for (int i = 1; i <= len1; ++i){//方便起见，i、j均指第i、j个字符,需要注意的是取字符串中字符时候的下标 for (int j = 1; j <= len2; ++j){ if (str1[i - 1] == str2[j - 1]){//处理相等的情况，这又包含了两种情况 if (str1[i - 1] != '*'){//情况1,两个普通字符相等 dp[i][j] = dp[i - 1][j - 1]; } else{//情况2,两个字符均为'*'; for (int index = i; index >= 0; --index){ dp[i][j] = dp[index][j - 1]; if (dp[i][j]) break; } for (int index = j; index >= 0; --index){ dp[i][j] = dp[i - 1][index]; if (dp[i][j]) break; } } }// end == else{//处理不相等的情况，这又包含了四种情况 if (str1[i - 1] != '?' && str1[i - 1] != '*'){//str1[i-1]是普通字符 if (str2[j - 1] != '?' && str2[j - 1] != '*'){//str2[j-1]也是普通字符 dp[i][j] = 0; } else if (str2[j - 1] == '?')//str2[j-1] == '?'; dp[i][j] = dp[i - 1][j - 1]; else {//str2[j-1] == '*'; for (int index = i; index >= 0; --index){ dp[i][j] = dp[index][j - 1]; if (dp[i][j]) break; } } } else if (str1[i - 1] == '?'){//str1[i-1] == '?' if (str2[j - 1] != '*'){//str2[j-1]是普通字符 dp[i][j] = dp[i - 1][j - 1]; } else {//str2[j-1] == '*' dp[i][j] = dp[i - 1][j - 2]; if (!dp[i][j]){ for (int index = i; index >= 0; --index){ dp[i][j] = dp[index][j - 1]; if (dp[i][j]) break; } } } } else {//str1[i-1] == '*' if (str2[j - 1] == '?'){//比普通的字符多一次匹配的机会 dp[i][j] = dp[i - 2][j - 1]; } if (!dp[i][j]){ for (int index = j; index >= 0; --index){ dp[i][j] = dp[i - 1][index]; if (dp[i][j]) break; } } } } }//end j }//end i return dp[len1][len2]; } }; int main() { string str1, str2; Solution s; while (cin >> str1 >> str2) if (s.isMatch(str1, str2)) cout << "true" << endl; else cout << "false" << endl; }
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
bool match_string(string str, string strpattern)
{
int nStr = str.size();
int nPatt = strpattern.size();
int** dp = new int*[nStr + 1];
for (int k = 0; k <= nStr; k++) {
dp[k] = new int[nPatt + 1];
memset(dp[k], 0, (nPatt + 1)*sizeof(int));
}
int t = 0;
while(strpattern[t] == '*')
{
for (int i = 0; i <= nPatt; ++i)
{
dp[t][i] = 1;
}
for (int j = 0; j < nStr; ++j){
dp[j][t] = 1;
}
++t;
}
dp[0][0] = 1;
for (int j = 1; j <= nPatt; ++j)
{
for (int i = 1; i <= nStr; ++i)
{
if ((strpattern[j - 1] == '?' && str[i - 1] != '\0') || strpattern[j - 1] == str[i - 1]){
dp[i][j] = dp[i - 1][j - 1];
}
else if (strpattern[j - 1] == '*'){
if (dp[i][j - 1] == 1 || dp[i - 1][j] == 1 || dp[i - 1][j - 1] == 1)
dp[i][j] = 1;
}
}
}
bool ret = (dp[nStr][nPatt] == 1 ? true : false);
for (int k = 0; k <= nStr; k++)
delete[] dp[k];
delete dp;
return ret;
}
int main(int argc, char** argv)
{
string s1, s2;
while (cin >> s1 >> s2){
if (match_string(s2, s1))
cout << "true" << endl;
else
cout << "false" << endl;
}
return 0;
}
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
bool solve(string str1,string str2)
{
if(str1.length()>str2.length())
return false;
int i,j;
for(i=0,j=0;i<str1.length(),j<str2.length();)
{
if(str1[i]=='?')
{
i++;
j++;
}
else if(str1[i]=='*')
{
//i++;j++;//只用这一句也能通过
if(i==str1.length()-1)
return true;
else if(i<str1.length()-1)
{
i++;j++;
}
}
else if(str1[i]!=str2[j])
return false;
else
{
i++;j++;
}
}
return true;
}
int main()
{
string str1,str2;
while(cin>>str1>>str2)
{
if(solve(str1,str2))
cout<<"true"<<endl;
else
cout<<"false"<<endl;
}
return 0;
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
