leetcode-regex.rs

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        match_regex(&s, &p)
    }
}

pub fn match_regex(text: &str, regex: &str) -> bool {
    let regex = parse_regex(regex);
    let text: Vec<_> = text.chars().collect();

    inner_match(&text, &regex)
}

fn inner_match(text: &[char], regex: &[Node]) -> bool {
    if text.is_empty() && regex.is_empty() {
        return true;
    }

    if regex.is_empty() && !text.is_empty() {
        return false;
    }

    let (token, operator) = regex.first().unwrap();

    match operator {
        Operator::None => {
            let char = match text.first() {
                Some(char) => *char,
                None => return false,
            };

            if token.matches(char) {
                inner_match(&text[1..], &regex[1..])
            } else {
                false
            }
        }

        Operator::Asterisk => {
            let max_matches = text.iter().take_while(|c| token.matches(**c)).count();

            for i in (0..=max_matches).rev() {
                if inner_match(&text[i..], &regex[1..]) {
                    return true;
                }
            }

            false
        }
    }
}

pub fn parse_regex(regex: &str) -> Vec<Node> {
    let mut nodes: Vec<Node> = Vec::with_capacity(20);

    let mut iter = regex.chars().peekable();

    loop {
        let token = match iter.next() {
            Some('.') => Token::Wildcard,
            Some('*') => unreachable!("Asterisk without a preceding character"),
            Some(char) => Token::Char(char),
            None => break,
        };

        let operator = match iter.next_if_eq(&'*') {
            Some(_) => Operator::Asterisk,
            None => Operator::None,
        };

        nodes.push((token, operator));
    }

    nodes
}

pub type Node = (Token, Operator);

#[derive(Debug)]
pub enum Token {
    /// Any non-special character
    Char(char),

    /// A single .
    Wildcard,
}

impl Token {
    fn matches(&self, char: char) -> bool {
        match self {
            Token::Char(c) => c == &char,
            Token::Wildcard => true,
        }
    }
}

#[derive(Debug)]
pub enum Operator {
    Asterisk,
    None,
}