30 剑指offer-动态规划求正则表达式匹配

问题描述：请实现一个函数用来匹配包含'.'和'*'的正则表达式，模式中的字符'.'表示任意一个字符，而‘*’表示它前面的字符可以出现任意次(含0次)，在本题中，匹配是指字符串的所有字符匹配整个模式
例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是"aa.a"和"ab*a"均不匹配

"aaa"与"a*"匹配

动态规划求解：定义两个字符串a和b，a是字符串，b是匹配模式，定义dp[i][j]为字符串的前i个字符是否与模式的前j个字符相匹配。如果都是字符若如果对应位置相等，则dp[i][j]=dp[i-1][j-1],如果b[j]位置为'.'则dp[i][j]=dp[i-1][j-1],如果b[j]位置为'*'则判断dp[i][j]=dp[i][j-2](消除前一个,如果为真需要continue),则需要判断dp[i-1][j]是否为真，若为真还需要保证dp[i-1][j-2]为false，保证这个‘*’并没有消除。否者不为真。

public Boolean isMatch(String a,String b)
{
Boolean dp[][]=new Boolean[a.length()+1][b.length()+1];
dp[0][0]=true;
for(int i=1;i<a.length();i++)
{
for(int j=1;j<b.length();j++)
{
//如果两者相等或模式匹配等于'.'则正确性与前面的元素一致只要匹配其一即可
if(a.charAt(i-1)==b.charAt(j-1)||b.charAt(j-1)=='.')
{
dp[i][j]=dp[i-1][j-1];
//在不满足条件一的情况下，如果模式匹配为'*'
}else if(b.charAt(j-1)=='*')
{
//看是否能消去模式匹配的前两个从而达到匹配的目的
if(dp[i][j-2])
{
dp[i][j]=dp[i][j-1];
//如果不能消去则判断是否任意匹配的问题，需要保证*有效用，则dp[i-1][j-2]必须为false
}else if((a.charAt(i-1)==a.charAt(i-2))&&dp[i-1][j-2]==false&&dp[i-1][j]==true)
{
//否则均为false
dp[i][j]=true;
}else
{
dp[i][j]=false;
}
}else
{
dp[i][j]=false;
}
}
}
return dp[a.length()][b.length()];
}