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

DP

挺讨厌做这种题目的，感觉情况太复杂。自己是写不出来。看看别人写的吧

Ref: https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation/2

1
2
3
4
5
6
7
8
1. If p.charAt(j) == s.charAt(i) then dp[i][j] = dp[i-1][j-1];
2. If p.charAt(j) == '.' then dp[i][j] = dp[i-1][j-1];
3. If p.charAt(j) == '*': here are two sub conditions:
	1. if p.charAt(j-1) != s.charAt(i) then dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
	2. if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.' then
          dp[i][j] = dp[i-1][j]   // in this case, a* counts as multiple a 
       or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
       or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty
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
public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
    boolean[][] state = new boolean[s.length() + 1][p.length() + 1];
    state[0][0] = true;
    // no need to initialize state[i][0] as false
    // initialize state[0][j]
    for (int j = 1; j < state[0].length; j++) {
        if (p.charAt(j - 1) == '*') {
            if (state[0][j - 1] || (j > 1 && state[0][j - 2])) {
                state[0][j] = true;
            }
        }
    }
    for (int i = 1; i < state.length; i++) {
        for (int j = 1; j < state[0].length; j++) {
            if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                state[i][j] = state[i - 1][j - 1];
            }
            if (p.charAt(j - 1) == '*') {
                if (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.') {
                    state[i][j] = state[i][j - 2];
                } else {
                    state[i][j] = state[i - 1][j] || state[i][j - 1] || state[i][j - 2];
                }
            }
        }
    }
    return state[s.length()][p.length()];
}