算法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.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

给一个字符串s和一个模板参数p，实现正则表达式中的 '.' 和 '*'。

'.' 匹配单个字符。
'*' 匹配零个或者多个前面的字符。

匹配应该覆盖整个字符串而不是部分。
注意：
s 可能为空，只会包含小写的a-z。
p可能为空，只会包含小写a-z和'.' 与'*' 两种字符。

解：
使用动态规划解决这道题：

1. 对应位置符号能匹配上，即 p.charAt(j) == s.charAt(i)，那么dp[i][j] = dp[i-1][j-1]，也就是前面能匹配上，就代表当前能匹配上。
2. 如果是一个点，p.charAt(j) == '.' ，那么dp[i][j] = dp[i-1][j-1]，也就是前面能匹配上，就代表当前能匹配上。
3. 如果是一个*，有两种情况，
   第一种，我们用*前面的字符去匹配s，匹配不上，那*只能为空，那么dp[i][j] = dp[i][j-2] ；
   能匹配上;或者*前面是个点，
   dp[i][j] = dp[i-1][j] //a* 表示多个 a
   or dp[i][j] = dp[i][j-1] //a* 表示 一个 a
   or dp[i][j] = dp[i][j-2] // a* 表示空的

以下为代码：

public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
    int sLen = s.length();
    int pLen = p.length();

    boolean[][] dp = new boolean[sLen + 1][pLen + 1];
    dp[0][0] = true;
    for (int i = 0; i < pLen; i++) {
        if (p.charAt(i) == '*' && dp[0][i - 1]) {// 只能找到a*这种情况
            dp[0][i + 1] = true;
        }
    }
    for (int i = 0; i < sLen; i++) {
        for (int j = 0; j < pLen; 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[sLen][pLen];
}