10. Regular Expression Matching

这道题比较难。。。如果是完整的正则表达式处理，应该要用到编译原理相关的知识吧。本题只需要处理.和*两个元字符即可。

我最开始用的是一种类似于greedy的策略，用两个指针i和j分别指向待匹配字符串s和正则字符串p，检查每一个字符s[i]和p[j]是否匹配，否则就尝试移动指针。如果最后i==s.length()&&j==p.length()，就返回true。这种方式确实能处理一些通常的case，但会有很多特殊的case无法处理，就只能加上各种if条件。。。搞得很复杂。

最关键的是这道题并不适合greedy，很可能s能匹配整个的p，同时s也能匹配p的一部分。比如abc和a*b*c*.*.*a*b*，如果按我之前的算法就会出错。

google后找到了一种dp解法。dp(i,j)表示s.substring(0,i)和p.substring(0,j)能匹配上（注意包括i和j）。于是有如下状态转移方程（直接抄来的，修改了一些）：

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.' : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(j-1) == s.charAt(i) or p.charAt(j-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

按照这种思路，我写了一个解法：

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        // 注意边界条件
        if (p.length() == 0)
            return s.length() == 0;
        // 这是一个辅助的dp数组，dp2(i)==true表示p从0到i可以匹配一个空字符，比如a*b*这种形式
        boolean[] dp2 = new boolean[p.length()];
        for (int i = 1; i < p.length(); i++) { // dp2(0)必定是false
            if (p.charAt(i) == '*') {
                if (i == 1)
                    dp2[i] = true;
                else
                    dp2[i] = dp2[i - 2];
            }
        }
        // 如果s是一个空字符串，整个p必须能匹配一个空字符串
        if (s.length() == 0)
            return dp2[p.length() - 1];

        // 接下来才是主要的dp过程
        boolean[][] dp = new boolean[s.length()][p.length()]; // 注意boolean默认值是false
        // 如果p是一个正确的正则，第一个字符不能是*，也不会有两个连续的*
        // 这里不考虑p异常的情况

        // 计算初始状态
        if (s.charAt(0) == p.charAt(0))
            dp[0][0] = true;
        if (p.charAt(0) == '.')
            dp[0][0] = true;

        // 开始计算dp数组，但是对于第一行要特殊处理下，要用到辅助数组dp2
        for (int i = 0; i < s.length(); i++) {
            // 注意列从1开始计算。对于第0列，除了dp(0,0)，都必定是false
            for (int j = 1; j < p.length(); j++) {
                if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
                    if (i == 0)
                        dp[i][j] = dp2[j - 1]; // 注意对第一行的特殊处理
                    else
                        dp[i][j] = dp[i - 1][j - 1];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
                        if (j - 2 >= 0)  // 注意数组越界
                            dp[i][j] = dp[i][j - 2];
                    } else {
                        // 同样注意对第一行的特殊处理和数组越界判断
                        dp[i][j] = dp[i][j - 1];
                        if (j - 2 >= 0)
                            dp[i][j] = dp[i][j] || dp[i][j - 2];
                        if (i == 0)
                            dp[i][j] = dp[i][j] || dp2[j];
                        else
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[s.length() - 1][p.length() - 1];
    }
}

这个解法可以AC，但总是感觉不太对劲。。。因为引入了一个辅助数组dp2，感觉很别扭。而且在计算时还要对第一行特殊处理，也不够优雅。对第一行特殊处理的原因是如果dp[i][j]=dp[i-1][j-1]，i-1有可能越界。引入dp2也是这个原因。

看了别人的解法，发现是我对“状态”的定义有些问题。dp(i,j)的正确定义是“s的前i个字符和p的前j个字符能匹配”，i和j不一定是数组下标。这样解法就优雅很多：

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        // 这个dp数组的第一行，就相当于我原来的dp2
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '*' && dp[0][i - 1]) {
                dp[0][i + 1] = true;
            }
        }
        // 我的每次for循环是计算dp[i][j]，而这里是计算dp[i+1][j+1]
        // 就是因为对状态的定义不同
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == s.charAt(i)) {
                    dp[i + 1][j + 1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    } else {
                        dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

这样也少了很多边界条件的检查，简洁很多。就是不太容易想到。

还有一种用递归的解法（回溯）。原理上和DP有点像，不列出了。其实很多时候DP就像是从头开始计算，而回溯是从尾部开始计算，二者互逆的感觉。。。