Leetcode Problem 678. Valid Parenthesis String

678. Valid Parenthesis String

Leetcode Solutions

Approach #: Greedy

  1. Initialize lo and hi to 0. These variables represent the lowest and highest possible number of open parentheses.
  2. Iterate through each character c in the string s.
    • If c is '(', increment both lo and hi.
    • If c is ')', decrement both lo and hi.
    • If c is '*', increment hi but decrement lo only if lo is greater than 0 (since * can be an empty string).
  3. After processing each character, if hi is less than 0, return false as we have more closing parentheses than opening ones.
  4. Ensure lo never goes below 0 as we cannot have a negative number of open parentheses.
  5. After the iteration, check if lo is 0. If it is, return true, indicating that the string can be a valid sequence of parentheses. Otherwise, return false.
UML Thumbnail

Approach #: Brute Force

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...