题目
实现一个简单的正则表达式匹配函数，其中模式串只包含点（.）和星号（*）两种特殊符号。
解决
- 正向递归
从前向后对比两个字符串中的字符，指针i指向str，指针j指向模式串pattern
出口：j扫描完成时，若i也扫描完成，则返回true，否则返回false
if(模式串的下一位不是*){
if(i、j匹配成功)
return 递归调用：i、j前移1位
}
else{
while(i、j匹配成功){
if(递归调用：i前移1位，j前移2位，结果为true)
return true
i前移1位（利用递归的跳出实现回溯）
}
return 递归调用：i不动，j前移2位
}
public boolean re(String str, String pattern, int i, int j){
int m = str.length();
int n = pattern.length();
if (j == m)
return i == n;
if (j==n-1 || pattern.charAt(j+1) != '*')//其实出口还有i扫描完j没扫描完的情况，但在i<m中处理了
return i<m && (str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.') && re(str, pattern, i+1, j+1);
if (j<n-1 && pattern.charAt(j+1) == '*'){
while(i<m && (str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.')){
if (re(str, pattern, i+1, j+2))
return true;
i ++;
}
}
return re(str, pattern, i, j+2);
}
- 反向递归
初始化指针i，j为两字符串的长度，从后向前扫描。若j-1指向字符不为*，且匹配成功，则i、j向后移1位并递归调用；若j-1指向字符*，则判断两种情况：
1.x*看作空串，即i不动j后移2位进行递归；
2.x*看作x，即j不动，i后移1位进行递归
上述任何一种情况为true，且能够使之后的匹配成功进行，即i-1与j-2指向字符相同，则为true
注意与前向递归不同，情况2在递归里j仍然指向*，因此在下一层递归里可以继续复制x
出口：
1.j扫描完成时i也扫描完则为true，否则为false
2.i扫描完成时j没有扫描完，则只有这种情况为true：剩余的模式串能够通过*消减成空串
public boolean re2(String str, String pattern, int i, int j){
if (j==0)
return i==0;
if (i==0)
return j>1 && pattern.charAt(j-1)=='*' && re2(str,pattern,i,j-2);
if (pattern.charAt(j-1)!='*')
return equal(str.charAt(i-1),pattern.charAt(j-1)) && re2(str,pattern,i-1,j-1);
return (re2(str,pattern,i,j-2) || re2(str,pattern,i-1,j)) && equal(str.charAt(i-1),pattern.charAt(j-2));
}
public boolean equal(char a, char b){
return b == '.' || a == b;
}
- 动态规划
dp[i][j]：字符串位置从0到i，和模式串位置从0到j的匹配情况
对于长度为n的字符串，要考虑其长度为0、1、...、n的情况，所以dp两个维的长度都要加1
边界：
1.dp[0][0] = true;
2.dp[0][j] 在模式串能够通过*消减为空串时为true，否则为false
其余元素的计算逻辑类似于方法2
public static boolean re3(String str, String pattern){
int m = str.length();
int n = pattern.length();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for (int b=1;b<=n;b++){
dp[0][b] = b>1 && pattern.charAt(b-1)=='*' && dp[0][b-2];
}
for (int p=1;p<=m;p++){
for (int q=1;q<=n;q++){
if (pattern.charAt(q-1)!='*')
dp[p][q] = equal(str.charAt(p-1),pattern.charAt(q-1)) && dp[p-1][q-1];
else{
dp[p][q] = (dp[p][q-2] || dp[p-1][q]) && equal(str.charAt(p-1),pattern.charAt(q-2));
}
}
}
return dp[m][n];
}
public boolean equal(char a, char b){
return b == '.' || a == b;
}
