10. Regular Expression Matching

发表于 | 分类于

Implement regular expression matching with support for ‘.’ and ‘*’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

解法1： DP O(MN)

这题一开始拿到没想到可以用DP。如果从基础的递归开始思考的话会比较容易一点往dp的方向上想。
而dp的状态方程也不太好想。
参考了YouTube上的这个视频,讲的还是比较清楚的。
首先，dp[i][j]表示的是前i个字符和前j个字符是否能match。
那么如果s[i] == p[j]，又或者当前的pattern是”.”, 则可以轻松得出dp[i][j] = dp[i - 1][j - 1]
如果是,那么就稍微麻烦一点。
这里可以考虑的是两种情况：
一个是不match前面的字符，这种情况下可以得到dp[i][j] = dp[i][j - 2]
另外一个是match一个或者多个前面的字符，但是这种情况需要满足s[i] = p[j - 1].
那么怎么表示match呢？可以的做法就是把当前s的位置的字符删除，变成s[i - 1]再和p[i]尝试match.
举一个例子：aa 和a*。　如果在match第二个a的时候，可以退化成比较a和a*。而这个结果已经有了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) return true;
        if (s == null || p == null) return false;
        if (s.length() == 0 && p.length() == 0) return true;
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 2; i <= n; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || (p.charAt(j - 1) == s.charAt(i - 1))) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];    // zero match of the previous value
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] |= dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}