99. Recover Binary Search Tree

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;
use rustgym_util::*;
use std::mem::swap;

trait Inorder {
    fn inorder(&self, prev: &mut TreeLink, first: &mut TreeLink, second: &mut TreeLink);
}

impl Inorder for TreeLink {
    fn inorder(&self, prev: &mut TreeLink, first: &mut TreeLink, second: &mut TreeLink) {
        if let Some(node) = self {
            let node = node.borrow();
            node.left.inorder(prev, first, second);
            if let Some(prev_val) = prev.clone() {
                if prev_val.borrow().val >= node.val {
                    if first.is_none() {
                        *first = prev.clone();
                    }
                    *second = self.clone();
                }
            }
            *prev = self.clone();
            node.right.inorder(prev, first, second);
        }
    }
}

impl Solution {
    fn recover_tree(root: &mut TreeLink) {
        let mut prev = None;
        let mut first = None;
        let mut second = None;
        root.inorder(&mut prev, &mut first, &mut second);
        swap(
            &mut first.unwrap().borrow_mut().val,
            &mut second.unwrap().borrow_mut().val,
        )
    }
}

#[test]
fn test() {
    let mut root = tree!(1, tree!(3, None, tree!(2)), None);
    Solution::recover_tree(&mut root);
    let res = tree!(3, tree!(1, None, tree!(2)), None);
    assert_eq!(root, res);
    let mut root = tree!(3, tree!(1), tree!(4, tree!(2), None));
    Solution::recover_tree(&mut root);
    let res = tree!(2, tree!(1), tree!(4, tree!(3), None));
    assert_eq!(root, res);
}

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