Valid parenthesis string

String Dynamic Programming Stack Greedy

39.8% acceptance

Feb 20, 2026

6948

220

Given a string s containing '(', ')' and '*', return true if it is valid. '*' can be treated as '(', ')' or ''.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn check_valid_string(s: String) -> bool {
    let mut min_open = 0i32;
    let mut max_open = 0i32;
    for c in s.chars() {
      match c {
        '(' => { min_open += 1; max_open += 1; }
        ')' => { min_open -= 1; max_open -= 1; }
        '*' => { min_open -= 1; max_open += 1; }
        _ => {}
      }
      if max_open < 0 { return false; }
      if min_open < 0 { min_open = 0; }
    }
    min_open == 0
  }
}