10. Regular Expression Matching Hard

1/**
2 * [10] Regular Expression Matching
3 *
4 * Given an input string s and a pattern p, implement regular expression
5 * matching with support for '.' and '*' where:
6 *
7 * '.' Matches any single character.​​​​
8 * '*' Matches zero or more of the preceding element.
9 *
10 * The matching should cover the entire input string (not partial).
11 *  
12 * Example 1:
13 *
14 * Input: s = "aa", p = "a"
15 * Output: false
16 * Explanation: "a" does not match the entire string "aa".
17 *
18 * Example 2:
19 *
20 * Input: s = "aa", p = "a*"
21 * Output: true
22 * Explanation: '*' means zero or more of the preceding element, 'a'.
23 * Therefore, by repeating 'a' once, it becomes "aa".
24 *
25 * Example 3:
26 *
27 * Input: s = "ab", p = ".*"
28 * Output: true
29 * Explanation: ".*" means "zero or more (*) of any character (.)".
30 *
31 * Example 4:
32 *
33 * Input: s = "aab", p = "c*a*b"
34 * Output: true
35 * Explanation: c can be repeated 0 times, a can be repeated 1 time.
36 * Therefore, it matches "aab".
37 *
38 * Example 5:
39 *
40 * Input: s = "mississippi", p = "mis*is*p*."
41 * Output: false
42 *
43 *  
44 * Constraints:
45 *
46 * 1 <= s.length <= 20
47 * 1 <= p.length <= 30
48 * s contains only lowercase English letters.
49 * p contains only lowercase English letters, '.', and '*'.
50 * It is guaranteed for each appearance of the character '*',
51 * there will be a previous valid character to match.
52 *
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/regular-expression-matching/
57// discuss: https://leetcode.com/problems/regular-expression-matching/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn is_match(s: String, p: String) -> bool {
63        if !p.is_empty() && &p[0..1] == "*" {
64            return false;
65        }
66
67        let s_c: Vec<char> = s.chars().collect();
68        let p_c: Vec<char> = p.chars().collect();
69        // dp[i][j] - s[0..i] match p[0..j]
70        let mut dp = vec![vec![false; p_c.len() + 1]; s_c.len() + 1];
71        dp[0][0] = true;
72
73        // p[0..j] matches empty iff
74        // p[j - 1] is '*' and p[0..j - 2] matches empty
75        for j in 2..p_c.len() + 1 {
76            dp[0][j] = '*' == p_c[j - 1] && dp[0][j - 2];
77        }
78
79        for i in 1..s_c.len() + 1 {
80            for j in 1..p_c.len() + 1 {
81                if '*' != p_c[j - 1] {
82                    // s[0..i] match p[0..j] and s[i] matchs p[j]
83                    dp[i][j] = dp[i - 1][j - 1] && Self::_match(s_c[i - 1], p_c[j - 1]);
84                } else {
85                    // s[0..i + 1] match p[0..j - 1], this means * matchs 0 p[j - 1], or
86                    // s[0..i] match p[0..j + 1] and s[i - 1] matchs p[j - 2], so * matchs s[i] as well
87                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && Self::_match(s_c[i - 1], p_c[j - 2]);
88                }
89            }
90        }
91        dp[s.len()][p.len()]
92    }
93
94    fn _match(x: char, y: char) -> bool {
95        x == y || y == '.'
96    }
97}
98
99// submission codes end
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn test_10() {
107        assert!(Solution::is_match("aa".into(), "a*".into()));
108        assert!(!Solution::is_match("aa".into(), "a".into()));
109        assert!(!Solution::is_match("aa".into(), "ab".into()));
110        assert!(!Solution::is_match("mississippi".into(), "mis*is*p*.".into()));
111        assert!(Solution::is_match("ab".into(), "x*a*b*".into()));
112    }
113}
114