Solution for https://leetcode.com/problems/regular-expression-matching

regex_solution.rs

use std::collections::HashMap;

#[derive(Copy, Clone)]
enum MatchPattern { Any, Exact(u8) }

#[derive(Copy, Clone)]
enum OpCode { Match(MatchPattern), KleeneStar(MatchPattern) }

#[derive(Copy, Clone)]
struct Cursor<'a, T: Copy> { parts: &'a[T], cursor: usize }
impl<'a, T: Copy> Cursor<'a, T> {
    pub fn new(parts: &'a[T]) -> Self { Self { parts, cursor: 0 } }
    pub fn current(&self) -> Option<T> {
        if self.cursor >= self.parts.len() { None} else { Some(self.parts[self.cursor]) }
    }
    pub fn advance(&mut self) { self.cursor += 1; }
    pub fn position(&self) -> usize { self.cursor }
}

fn parse_op_codes(p: String) -> Vec<OpCode> {
    let mut op_codes = Vec::with_capacity(32); 
    for &b in p.as_bytes() {
        match b {
            b'.' => { op_codes.push(OpCode::Match(MatchPattern::Any)); },
            b'*' => {
                let last_id = op_codes.len() - 1;
                match op_codes[last_id] {
                    OpCode::Match(match_pattern) => op_codes[last_id] = OpCode::KleeneStar(match_pattern),
                    _ => unreachable!()
                }
            },
            _ => op_codes.push(OpCode::Match(MatchPattern::Exact(b)))
        }
    }
    op_codes
}

fn solve(op_code_cursor: Cursor<OpCode>, string_cursor: Cursor<u8>, memo: &mut HashMap<(usize, usize), bool>) -> bool {
    let mut op_code_cursor = op_code_cursor;
    let mut string_cursor = string_cursor;
    
    let lookup = (op_code_cursor.position(), string_cursor.position());
    
    if let Some(memo_entry) = memo.get(&lookup) {
        return *memo_entry;
    }
    
    let memo_entry = match op_code_cursor.current() {
        None => string_cursor.current().is_none(),
        Some(op_code) => {
            match string_cursor.current() {
                None => {
                    // The only valid configuration here is an existance of trailing Kleene stars
                    // Since there could be many Kleene stars, we are drainging them all
                    while let Some(OpCode::KleeneStar(_)) = op_code_cursor.current() {
                        op_code_cursor.advance();
                    }

                    // Check if op_code_cursor is drained completely.
                    // If so, we found a valid match
                    op_code_cursor.current().is_none()
                },
                Some(code) => match op_code {
                    OpCode::Match(MatchPattern::Any) => {
                        op_code_cursor.advance(); string_cursor.advance(); solve(op_code_cursor, string_cursor, memo)
                    },
                    OpCode::Match(MatchPattern::Exact(expected_code)) => {
                        expected_code == code && {
                            op_code_cursor.advance(); string_cursor.advance(); solve(op_code_cursor, string_cursor, memo)
                        }
                    },
                    OpCode::KleeneStar(match_pattern) => {
                        // We are first fork and check if there is a solution for the case of a missing character
                        let mut op_code_cursor_fork = op_code_cursor;
                        op_code_cursor_fork.advance();
                        solve(op_code_cursor_fork, string_cursor, memo) || {
                            // If there is no such solution, we are checking the branch where a character should exist
                            string_cursor.advance();
                            match match_pattern {
                                MatchPattern::Any => solve(op_code_cursor, string_cursor, memo),
                                MatchPattern::Exact(expected_code) => 
                                    expected_code == code && 
                                    solve(op_code_cursor, string_cursor, memo)
                            }
                        }
                    }
                }
            }
        }
    };
    
    memo.insert(lookup, memo_entry);
    memo_entry
}

impl Solution {
    pub fn is_match(s: String, p: String) -> bool { 
        // We can memoize results for specific positions in cursors, and we definitely will do this :)
        let mut memo: HashMap<(usize, usize), bool> = HashMap::new();
        
        let op_codes = parse_op_codes(p);
        solve(Cursor::new(&op_codes), Cursor::new(s.as_bytes()), &mut memo)
    }
}