learning/l33tcode_rs/src/regular_expression_matching.rs at master · fspv/learning · 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
#[allow(dead_code)]
struct Solution;

use std::collections::HashMap;

fn dfs(
    string_pos: usize,
    pattern_pos: usize,
    string: &Vec<char>,
    pattern: &Vec<char>,
    cache: &mut HashMap<(usize, usize), bool>,
) -> bool {
    if let Some(cached) = cache.get(&(string_pos, pattern_pos)) {
        return *cached;
    }

    if string_pos == string.len() || pattern_pos == pattern.len() {
        if pattern.get(pattern_pos + 1) == Some(&'*') {
            return dfs(string_pos, pattern_pos + 2, string, pattern, cache);
        }

        return string_pos == string.len() && pattern_pos == pattern.len();
    }

    let mut result = false;

    match pattern.get(pattern_pos) {
        Some('.') => match pattern.get(pattern_pos + 1) {
            Some('*') => {
                result = result
                    || dfs(string_pos + 1, pattern_pos + 2, string, pattern, cache)
                    || dfs(string_pos + 1, pattern_pos, string, pattern, cache)
                    || dfs(string_pos, pattern_pos + 2, string, pattern, cache);
            }
            _ => {
                result = result || dfs(string_pos + 1, pattern_pos + 1, string, pattern, cache);
            }
        },
        _ => match pattern.get(pattern_pos + 1) {
            Some('*') => {
                if string[string_pos] == pattern[pattern_pos] {
                    result = result
                        || dfs(string_pos + 1, pattern_pos + 2, string, pattern, cache)
                        || dfs(string_pos + 1, pattern_pos, string, pattern, cache)
                        || dfs(string_pos, pattern_pos + 2, string, pattern, cache);
                } else {
                    result = result || dfs(string_pos, pattern_pos + 2, string, pattern, cache);
                }
            }
            _ => {
                if string[string_pos] == pattern[pattern_pos] {
                    result = result || dfs(string_pos + 1, pattern_pos + 1, string, pattern, cache);
                }
            }
        },
    }

    cache.insert((string_pos, pattern_pos), result);

    result
}

impl Solution {
    #[allow(dead_code, clippy::needless_pass_by_value)]
    pub fn is_match(s: String, p: String) -> bool {
        let mut cache: HashMap<(usize, usize), bool> = HashMap::new();
        dfs(0, 0, &s.chars().collect(), &p.chars().collect(), &mut cache)
    }
}