首先给出一个递归的思路：
public class Solution {
public static boolean isMatch(String s, String p) {}
不过显然太废时是过不了的。
再给一个动态规划的思路：F[i][j]表示s的前i个字符和p的前j个字符是否匹配。注意的是F[0][0]是s,p皆为空串的情况。
动规的方程是这样的，对于s的第i个字符(i>0，s.charAt(i-1))，得到其他F[i][j]后，再求所有的F[i+1][j]。
F[i+1][0]显然是false，初始化所有的F[i+1][j]为false。
如果F[i][j]=ture：
对于s[i]==p[j]||p[j]=='?'的情况，显然F[i+1][j+1]=true
若p[j-1]=="*"，说明p的前j个字符仍然能适配s的i+1个字符，F[i+1][j]=true（一个*对多个字符的情况）
如果F[i][j]=false：
若p[j-1]=="*"，并且F[i][j-1]=true，说明p的第j个字符‘*’对应0个字符，F[i+1][j]=true;（一个*对应0个字符）
public class Solution {
public static boolean isMatch(String s, String p)
{
int i,j;
int n=s.length();
int m=p.length();
if(n>32310)
return false;
boolean[][] F=new boolean[2][m+1];
F[0][0]=true;
for(j=1;j<=m;j++)
{
if(F[0][j-1]==true && p.charAt(j-1)=='*')
{
F[0][j]=true;
}
else
F[0][j]=false;
//System.out.print(j+":"+F[0][j]+" ");
}
for(i=0;i<n;i++)
{
//initialize
for(j=0;j<=m;j++)
{
F[(i+1)%2][j]=false;
}
//dp
F[(i+1)%2][0]=false;
for(j=0;j<=m;j++)
{
if(F[i%2][j]==true)
{
if(j<m)
{
if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='?')
F[(i+1)%2][j+1]=true;
}
if(j>0 && p.charAt(j-1)=='*')
F[(i+1)%2][j]=true;
}
else
{
if(j>0 && p.charAt(j-1)=='*'&&F[(i+1)%2][j-1]==true)
F[(i+1)%2][j]=true;
}
}
}
return F[n%2][m];
}
}