35 动态规划解通配符匹配问题

问题描述：给定一个字符串(s)和一个字符模式(p),实现一个支持"?"和"*"的通配符匹配，只有两个字符串完全匹配才算匹配成功，说明：s可能为空，且只能包含a-z的小写字母，p可能为空，且只包含a-z的小写字母以及字符"?"和"*"两种。

动态规划分析：定义dp[i][j]为前i个元素与前j个元素是否匹配，对于j为"*"的情况，从i往前找直到dp[i-k][j-1]==true,则dp[i][j]==true,否则为false

public Boolean isMatch(String s,String p)
{
if(s.length()==0||p.length()==0)
{
if((s.length()==0&&p.length()==0))
{
return true;
}else if(s.length()==0&&p.length()!=0)
{
for(int i=0i<p.length();i++)
{
if(p.charAt(i)!='*')
{
return false;
}
}
return true;
}else
{
return false;
}
}
Boolean dp[][]=new Boolean[s.length()][p.length()];
if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='*')
{
dp[0][0]=true;
}else
{
dp[0][0]=false;
}
for(int i=1;i<s.length();i++)
{
for(int j=1;j<p.length();j++)
{
if('a'<=p.charAt(j)<='z')
{
if(p.charAt(j)==a.charAt(i))
{
dp[i][j]=dp[i-1][j-1];
}else
{
dp[i][j]=false;
}
}else if(p.charAt(j)=='?')
{
dp[i][j]=dp[i-1][j-1];
}else
{
dp[j][j]=false;
for(int k=i;k>0;k++)
{
if(dp[i][j-1])
{
dp[i][j]=true;
continue;
}
}
}
}
}
return dp[s.length()][p.length()];
}