题意：给出字符串s和正则p，s只包含小写英文字符，p只包含小写英文字符和.和*。在*之前必定有英文字符。

10. Regular Expression Matching (opens new window)

当p中没有*，处理很简单，直接比较s和p就行了。当p中出现*，这时有两种情况，一种是s选择不匹配，另一种选择匹配。使用递归处理即可。

boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
// 分两种情况
// 1.不匹配s，跳过
// 2.匹配s的1个字符
if (p.length() >= 2 && p.charAt(1) == '*') {
    return isMatch(s, p.substring(2)) 
        || (firstMatch && isMatch(s.substring(1), p));
} else {
    return firstMatch && isMatch(s.substring(1), p.substring(1));
}

但是上面的代码速度很慢，因为有大量重复的计算，大量的substring方法调用也很浪费空间。中间的计算结果可以使用一个二维数组保存，字符串的截取也可以改为对二维数组的计算。

enum Result {
    TRUE,
    FALSE
}

class Solution {

    Result[][] memo;

    public boolean isMatch(String s, String p) {
        memo = new Result[s.length() + 1][p.length() + 1];
        return dp(0, 0, s, p);
    }

    private boolean dp(int i, int j, String s, String p) {
        if (memo[i][j] != null) {
            return memo[i][j] == Result.TRUE;
        }
        boolean ans;
        if (j == p.length()) {
            // 边界情况
            // 当p超出边界，s未超出表示match失败，超出表示match成功
            ans = i == s.length();
        } else {
            boolean firstMatch = (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'));
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                ans = dp(i, j + 2, s, p) 
                    || firstMatch && dp(i + 1, j, s, p);
            } else {
                ans = firstMatch && dp(i + 1, j + 1, s, p);
            }
            memo[i][j] = ans ? Result.TRUE : Result.FALSE;
        }
        return ans;
    }
}