LeetCode/10. Regular Expression Matching (Dynamic Programming) 20.4.19 Hard at master · BrianSong/LeetCode · GitHub

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
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 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


Solution: ------------ Dynamic Programming ----------- https://www.youtube.com/watch?v=DqhPJ8MzDKM&t=8s (看讲题思路不要看代码，代码是反的)
----------------------- O(len(s)*len(p)) T O(len(s)*len(p)) S
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        match = [[False for i in range(len(s) + 1)] for j in range(len(p) + 1)]   # Step no.1: state
        match[0][0] = True                                                        # Step no.2: init, match[0][0] is TRUE !!!!
        for i in range(1, len(p) + 1):
            if p[i - 1] == '*':                                                   # when * => zero of preceding element
                match[i][0] = match[i - 2][0]
        for i in range(1, len(p) + 1):                                            # Step no.3: transform function
            for j in range(1, len(s) + 1):
                if s[j - 1] == p[i - 1] or p[i - 1] == '.':                       # First when the current characters are the same
                                                                                  # or p[i - 1] == '.'
                    match[i][j] = match[i - 1][j - 1]
                elif p[i - 1] == '*':                                             # Second when p[i - 1] == '*'
                    if s[j - 1] == p[i - 2] or p[i - 2] == '.':                   # When '*' => more of the preceding element
                                                                                  # For example, abcdd == abcd* == abc.*
                                                                                  # because d == d == . and abcd == abcd* == abc.*
                                                                                  # it's like ok, s can have one more character
                                                                                  # as long as it is the same as the character before *,
                                                                                  # in this way, we can duplicate it,
                                                                                  # and turn it into the T or F of its preceding matches
                        match[i][j] = match[i][j - 1]
                    match[i][j] = match[i][j] or match[i - 2][j]                  # And, of course, it still satisfies the general case
                                                                                  # as in the init step
                                                                                  # Just like in the init step, '*' => zero
                                                                                  # For example, abcd == abcde*
        return match[-1][-1]                                                      # Step no.4: return


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