[LeetCode每日一题]10. Regular Expression Matching

题目如下：

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element

10. Regular Expression Matching
这道题让我们实现一个对包含小写字母，’.’ 以及 ‘‘的正则表达式，看到这道题的第一个想法是先构造一个NFA，再用字符串进行匹配。然而这道题的标签是DP，就没有去实现。想了半天没想出来就去看了solution，给了两种解法，一个递归，一个DP，DP其实是将递归方法的中间结果保存起来。
首先来看递归方法。
1.定义返回条件
2.用firstMatch保存第一个字符是否匹配
3.看regExp的第二个字符是否为
若是，有两种情况可能匹配成功
（1）regExp前两个字符没用到被跳过
（2）regExp前两个字符用到（*闭包），字符串第1个字符之后的子串也和regExp匹配，且第1个字符匹配成功（firstMatch==true）
若不是，则第一个字符要匹配成功（firstMatch==true），且字符串和regExp都去掉第一个字符也要匹配才算匹配成功
实现代码如下：

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean firstMatch = s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        if (p.length() > 1 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
        }
        return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
}

将上述递归过程改成DP的形式，用dp[i][j]表示s从第i个字符到结尾的子串s[i:]和p从第j个字符到结尾的子串p[j:]是否匹配。初始条件为dp[s.length][p.length] == true,即二者均为空时的情况。i，j从大往小推到。
实现代码如下：

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }

        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;

        for (int i = s.length(); i >= 0; i--) {
            for (int j = p.length() - 1; j >= 0; j--) {
                boolean firstMatch =i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    dp[i][j] = (j + 2 <= p.length() && dp[i][j + 2]) || (firstMatch && dp[i + 1][j]);
                } else {
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}