LeetCode 10. Regular Expression Matching

[Woodyiiiiiii]

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:

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 preceding 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

---

我没做出来这道Hard难度的题目。这道题难点在于如何分类字符串s和字符串p，然后两两比对。看了大佬的博客，这道题有两种解法。

第一种是暴力递归，将字符串s和p这样分类——对s和p只做最多前两个字符的判断：

1. 如果p为空，判断s是否为空
2. 如果p的长度等于1，判断s是否为空，若不空，判断s的首字符是否等于p的首字符或者p的首字符是'.'(任意字符)
3. 如果p的长度大于2，且p的第二个字符不是'*'(循环字符)，判断s的首字符是否等于p的首字符或者p的首字符是'.'(任意字符)，然后将两个字符串的首字符去除，对两个子字符串作递归判断
4. 如果p的长度大于2，且p的第二个字符是'*'(循环字符)，进一步，如果s的首字符等于p的首字符或者p的首字符是'.'(任意字符)，则先递归判断去除p的前两个字符的子字符串，若返回结果为假则递归判断去除s的首字符的子字符串；如果进一步的条件不满足，递归判断去除p的前两个字符的子字符串
   这四种情况的判断顺序是从1到4的，如此循环切分判断。

代码如下：

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

注意Java中的substring函数，如果参数有两个，第一个参数从0开始，包含进得到的子字符串中，第二个参数从0开始，不包含进得到的子字符串中；如果参数只有一个，相当于第二个参数为字符串长度的前者。

第二种方法是动态规划DP。我们从暴力解法可以看出原问题可以分成多个子问题，每个问题由其子问题来决定其解，而且具有无效性，所以可以使用DP解法。

思路是：定义一个二维的 DP 数组，其中 dp[i][j] 表示 s[0,i) 和 p[0,j) 是否匹配，然后有下面三种情况：

1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '' and the pattern repeats for 0 times;
3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j > 1 && p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]
                            || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2)
                                            || p.charAt(j - 2) == '.') && dp[i - 1][j]);
                }else {
                    dp[i][j] = i > 0 &&
                            dp[i - 1][j - 1]
                            && (s.charAt(i - 1) == p.charAt(j - 1)
                                    || p.charAt(j - 1) == '.');
                }
            }
        }
        return dp[m][n];
    }
}

DP解法就是暴力递归解法的分类思路，只不过多消耗了空间不用去递归而已。

---

参考资料：

• https://leetcode.com/problems/regular-expression-matching/
• [LeetCode] 10. Regular Expression Matching grandyang/leetcode#10