RUST GYM v0.2.11

44. Wildcard Matching

Given an input string (s) and a pattern (p), 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'.

Example 4:

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input: s = "acdcb", p = "a*c?b"
Output: false

 

Constraints:

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

Rust Solution

struct Solution;

impl Solution {
    fn is_match(s: String, p: String) -> bool {
        let n = s.len();
        let m = p.len();
        let s: Vec<char> = s.chars().collect();
        let p: Vec<char> = p.chars().collect();
        let mut memo: Vec<Vec<Option<bool>>> = vec![vec![None; m + 1]; n + 1];
        Self::is_match_dp(n, m, &mut memo, &s, &p)
    }

    fn is_match_dp(
        n: usize,
        m: usize,
        memo: &mut Vec<Vec<Option<bool>>>,
        s: &[char],
        p: &[char],
    ) -> bool {
        if let Some(ans) = memo[n][m] {
            ans
        } else {
            let res = if n == 0 && m == 0 {
                true
            } else if n == 0 && m != 0 {
                if p[m - 1] == '*' {
                    Self::is_match_dp(n, m - 1, memo, s, p)
                } else {
                    false
                }
            } else if n != 0 && m == 0 {
                false
            } else {
                if s[n - 1] == p[m - 1] {
                    Self::is_match_dp(n - 1, m - 1, memo, s, p)
                } else {
                    match p[m - 1] {
                        '?' => Self::is_match_dp(n - 1, m - 1, memo, s, p),
                        '*' => {
                            Self::is_match_dp(n - 1, m, memo, s, p)
                                || Self::is_match_dp(n, m - 1, memo, s, p)
                        }
                        _ => false,
                    }
                }
            };

            memo[n][m] = Some(res);
            res
        }
    }
}

#[test]
fn test() {
    let s = "aa".to_string();
    let p = "a".to_string();
    let res = false;
    assert_eq!(Solution::is_match(s, p), res);
    let s = "aa".to_string();
    let p = "*".to_string();
    let res = true;
    assert_eq!(Solution::is_match(s, p), res);
    let s = "cb".to_string();
    let p = "?a".to_string();
    let res = false;
    assert_eq!(Solution::is_match(s, p), res);
    let s = "adceb".to_string();
    let p = "*a*b".to_string();
    let res = true;
    assert_eq!(Solution::is_match(s, p), res);
    let s = "acdcb".to_string();
    let p = "a*c?b".to_string();
    let res = false;
    assert_eq!(Solution::is_match(s, p), res);
}

Having problems with this solution? Click here to submit an issue on github.