题解 | #字符串通配符#
字符串通配符
http://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
使用动态规划
1.dp[0][0]=1，空串和空串匹配
1.串首的*可以和空串匹配，串首为*，dp[i][0]=1；
2.*时（*可以匹配0个或无限个合法字符），即为左边和上边的最大值，左边：用*继续做匹配；上边：忽略*
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
3.？时（只能匹配一个合法字符，且不能忽略?）
dp[i][j]=dp[i-1][j-1];4.字符相等时
dp[i][j]=dp[i-1][j-1];5.其他不满足上述条件的，dp[i][j]=0;
总代码：
/*HJ71 字符串通配符
动态规划
dp[i][j] pattern前i个，string前j个
*/
#include <iostream>
using namespace std;
int main()
{
string pattern;
string str;
int dp[100][100]={0};
cin>>pattern;
cin>>str;
dp[0][0]=1;
for(int i=0;i<pattern.length();i++)//全部转换为小写字母
{
if(pattern[i]>='A'&&pattern[i]<='Z') pattern[i]=pattern[i]-'A'+'a';
}
for(int i=0;i<str.length();i++)
{
if(str[i]>='A'&&str[i]<='Z') str[i]=str[i]-'A'+'a';
}
for(int i=1;pattern[i-1]=='*';i++) //串首的*可以跟空串匹配
{
dp[i][0]=1;
}
for(int i=1;i<=pattern.length();i++)//dp数组更新
for(int j=1;j<=str.length();j++)
{
if(pattern[i-1]=='*')
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//dp[i-1][j]：忽略*，dp[i][j-1]：用*做匹配该字符 (注意*可以匹配0个或者多个字符)
else if(pattern[i-1]=='?'&&(str[j-1]>='0'&&str[j-1]<='9'||str[j-1]>='a'&&str[j-1]<='z'))
dp[i][j]=dp[i-1][j-1];
else if(pattern[i-1]==str[j-1])
dp[i][j]=dp[i-1][j-1];
}
// for(int i=1;i<=pattern.length();i++)//dp数组打印
// {
// cout<<pattern[i-1];
// for(int j=1;j<=str.length();j++)
// {
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
if(dp[pattern.length()][str.length()])
cout<<"true"<<endl;
else cout<<"false"<<endl;
}
查看13道真题和解析
