LeetCode每日一题(44. Wildcard Matching)

Given an input string (s) and a pattern §, implement wildcard pattern matching with support for ‘?’ and ‘*’ where:

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Example 1:

Input: s = “aa”, p = “a”
Output: false

Explanation: “a” does not match the entire string “aa”.

Example 2:

Input: s = “aa”, p = “*”
Output: true

Explanation: ‘*’ matches any sequence.

Example 3:

Input: s = “cb”, p = “?a”
Output: false

Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, ‘?’ or ‘*’.

---

无非就是 pattern 的三种情况:
a-z: 严格匹配当前字符，然后匹配剩余 pattern
?: 跳过当前字符继续匹配剩余 pattern
*: 遍历后面的每一个字符作为起点匹配剩余的 pattern, 只要有一个可以成功则视为成功

---

use std::collections::HashMap;

impl Solution {
    fn is_all_stars(pattern: &Vec<char>, pi: usize) -> bool {
        for c in &pattern[pi..] {
            if c != &'*' {
                return false;
            }
        }
        true
    }
    fn match_pattern(
        chars: &Vec<char>,
        pattern: &Vec<char>,
        ci: usize,
        pi: usize,
        cache: &mut HashMap<(usize, usize), bool>,
    ) -> bool {
        if ci == chars.len() {
            if pi == pattern.len() || Solution::is_all_stars(pattern, pi) {
                return true;
            }
            return false;
        }
        if pi == pattern.len() {
            return false;
        }
        let c = chars[ci];
        let p = pattern[pi];
        match p {
            '?' => {
                let ans = if let Some(c) = cache.get(&(ci + 1, pi + 1)) {
                    *c
                } else {
                    Solution::match_pattern(chars, pattern, ci + 1, pi + 1, cache)
                };
                cache.insert((ci, pi), ans);
                return ans;
            }
            '*' => {
                if pi == pattern.len() - 1 {
                    return true;
                }
                for ni in ci..chars.len() {
                    let next = if let Some(c) = cache.get(&(ni, pi + 1)) {
                        *c
                    } else {
                        Solution::match_pattern(chars, pattern, ni, pi + 1, cache)
                    };
                    if next {
                        return true;
                    }
                }
                cache.insert((ci, pi), false);
                return false;
            }
            _ => {
                if c != p {
                    return false;
                }
                let next = if let Some(c) = cache.get(&(ci + 1, pi + 1)) {
                    *c
                } else {
                    Solution::match_pattern(chars, pattern, ci + 1, pi + 1, cache)
                };
                cache.insert((ci, pi), next);
                return next;
            }
        }
    }

    pub fn is_match(s: String, p: String) -> bool {
        let chars: Vec<char> = s.chars().collect();
        let pattern: Vec<char> = p.chars().collect();
        Solution::match_pattern(&chars, &pattern, 0, 0, &mut HashMap::new())
    }
}

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