Regular expression matching

String Dynamic Programming Recursion

30.5% acceptance

Jan 12, 2026

13251

2393

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. Return a boolean indicating whether the matching covers the entire input string (not partial).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn is_match(s: String, p: String) -> bool {
    let s_bytes = s.as_bytes();
    let p_bytes = p.as_bytes();
    let m = s_bytes.len();
    let n = p_bytes.len();
    
    // dp[i][j] represents if first i chars of s match first j chars of p
    let mut dp = vec![vec![false; n + 1]; m + 1];
    
    // Empty string matches empty pattern
    dp[0][0] = true;
    
    // Handle patterns like a*, a*b*, a*b*c* that can match empty string
    for j in 2..=n {
      if p_bytes[j - 1] == b'*' {
        dp[0][j] = dp[0][j - 2];
      }
    }
    
    // Fill the DP table
    for i in 1..=m {
      for j in 1..=n {
        let s_char = s_bytes[i - 1];
        let p_char = p_bytes[j - 1];
        
        if p_char == b'*' {
          // '*' matches zero or more of the preceding element
          let prev_p_char = p_bytes[j - 2];
          
          // Case 1: Use * to match zero of preceding element
          dp[i][j] = dp[i][j - 2];
          
          // Case 2: Use * to match one or more of preceding element
          // Only if the preceding element matches current char in s
          if prev_p_char == s_char || prev_p_char == b'.' {
            dp[i][j] = dp[i][j] || dp[i - 1][j];
          }
        } else if p_char == b'.' || p_char == s_char {
          // '.' matches any character or exact character match
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }
    
    dp[m][n]
  }
}