LeetCode 题解-10. Regular Expression Matching

对Leetcode 10. Regular Expression Matching 题目的求解。

Problem Description#

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#

1
Input :
2
s = "aa"
3
p = "a"
4
Output: false
5
Explanation: "a" does not match the entire string "aa".

Example 2#

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

Example 3#

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

Example 4#

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

Example 5#

1
Input:
2
s = "mississippi"
3
p = "mis*is*p*."
4
Output: false

Analysis#

这道题目要求我们实现一个正则匹配的引擎，包括*和.．我刚开始想用贪心匹配解决，发现不能解决全串匹配的问题，也就是说，贪心匹配不保证我们考虑到所有可能的情况．根据leetcode discussion提供的思路，我们使用动态规划的方法解决此问题．

我们开辟二维数组dp[i][j]来表示我们是否可以用p[0…j]的正则表达式成功匹配s[0…i]的字符串．递归公式我们可以这样考虑．假设我们在dp[i][j]之前已经计算好了dp[0…i-1][0..j-1]. 至于dp[i][j],我们考虑三种不同的情况，

1. s[i] == p[j]. 那么如果我们就可以继承dp[i-1][j-1].
1. p[j] == ’.’, 同样，我们可以继承dp[i-1][j-1].
1. p[j] == ’*’. 这意味着p[j-1] 是[a-z]的字符．所以我们需要将讨论p[j-1]与s[i]的关系．
- p[j-1] == ’.’ 或 p[j-1] == s[i]. 在这种情况下，我们可以有不同的可能，只要有一种可能能够成功匹配，我们就能成功匹配．　如果我们不适用`[a-z|.]*‘进行匹配，结果是dp[i][j] = dp[i][j-2]. 如果我们只匹配一次，dp[i][j] = dp[i][j-1]. (相当于不用*); 如果我们匹配多次，dp[i][j] = dp[i-1][j].
- p[j-1] 不能和s[i]进行匹配，即匹配失败．所以，dp[i][j] = dp[i][j-2];

最终返回dp[i][j]即为结果．

Solution#

需要注意的是在初始化的时候需要初始化dp[0][0..j].

1
class Solution {
2
    public static boolean isMatch(String s, String p){
3
        int dp[][] = new int [s.length()+1][p.length()+1];
4
        dp[0][0] = 1;
5
        for (int i = 1; i <= p.length(); ++i){
6
            if (p.charAt(i-1) == '*') dp[0][i] = dp[0][i-2];
7
        }
8
        for (int i = 1; i <= s.length(); ++i){
9
            for (int j = 1; j <= p.length(); ++j){
10
                if (p.charAt(j-1) == s.charAt(i-1)){
11
                    dp[i][j] = dp[i-1][j-1];
12
                }
13
                else if (p.charAt(j-1) == '.'){
14
                    dp[i][j] = dp[i-1][j-1];
15
                }
16
                else if (p.charAt(j-1) == '*'){
17
                    //in this condition, we have to check dp[i-1][j-1] and dp[i][j-1] and dp[i-1][j]
18
                    if (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.') {
19
                        dp[i][j] = dp[i][j-2] | dp[i-1][j] | dp[i][j-1];
20
                                // no matches | multiple matches | single match
21
                    }
22
                    else dp[i][j] = dp[i][j-2];
23
                }
24
                //default 0
25
            }
26
        }
27
        // for (int i = 0; i < s.length(); ++i){
28
        //     for (int j = 0; j < p.length(); ++j){
29
        //         System.out.printf("%d ", dp[i][j]);
30
        //     }
31
        //     System.out.println();
32
        // }
33
        if (dp[s.length()][p.length()] == 1) return true;
34
        return false;
35
    }
36
}