题目描述：
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（字符由英文字母，数字0-9和 '.' 组成，下同）
？：匹配1个字符
注意：匹配时不区分大小写。
输入：
通配符表达式；
一组字符串。
输出：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
本题含有多组样例输入！
输入描述：
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
输出描述：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
示例：
输入：
te?t*.*
txt12.xls
输出：
false
解题思路：
本题用动态规划解比递归要方便，而且速度也快些。输入两个字符串，按照各自的尺寸建立二维数组，并定义(0,0)点为true，其他默认为false；每一行首值的取值，取决于上一行首值和通配符字符串s1该位置字符是否为'*'，即当s2无字符时，s1只有首字符为'*'才能与其匹配；之后继续填充，首行数值均为false，即s1无字符时，无法进行匹配；从第二行第二列开始，一行行填充，若s1对应位置的字符为'*'，则该行的数值由其同行前列和同列前行决定，若其同列前行为true，表明之前的匹配均合理，再考虑到*可以匹配0个字符，所以该位置可以true，但注意，还要判断s2字符是否合理；若该行对应s1字符为正常字母数字，则进行正常比对，若同s2字符一致（不区分大小写），且其前列前行为true，则当前也为true，这是当前已经成功匹配的字符串位置；若s1字符为'?'，则只需判断s2字符是否合理，若合理且前列前行也为true，当前也为true。
动态规划的二维表遍历完，最终匹配结果就是v[m][n]。解题完毕。
测试代码：
#include <iostream> #include <string> #include <vector> using namespace std; // 判断字符是否符合要求 bool isOk(char c) { return (isalpha(c)||isalnum(c)||c=='.'); } bool Match(string s1,string s2) { int m = s1.size(); int n = s2.size(); vector<vector<bool>> v(m+1,vector<bool>(n+1,false)); v[0][0] = true; for(int i=1;i<=m;++i) { v[i][0] = v[i-1][0]&&(s1[i-1]=='*'); for(int j=1;j<=n;++j) { if(s1[i-1]=='*'){ if(isOk(s2[j-1])) { v[i][j] = v[i-1][j]||v[i][j-1]; } }else{ if(tolower(s1[i-1])==tolower(s2[j-1])) v[i][j] = v[i-1][j-1]; if(s1[i-1]=='?' && isOk(s2[j-1])) v[i][j] = v[i-1][j-1]; } } } return v[m][n]; } int main(void) { string s1,s2; while(cin>>s1>>s2) { if(Match(s1, s2)){ cout << "true" << endl; }else{ cout << "false" << endl; } } return 0; }
