题目

实现一个简单的正则表达式匹配函数，其中模式串只包含点（.）和星号（*）两种特殊符号。

解决

1. 正向递归
   从前向后对比两个字符串中的字符，指针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);
}

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;
}

3. 动态规划
   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;
}