678. Valid Parenthesis String LeetCode Solution

In this guide, you will get 678. Valid Parenthesis String LeetCode Solution with the best time and space complexity. The solution to Valid Parenthesis String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Valid Parenthesis String solution in C++
Valid Parenthesis String solution in Java
Valid Parenthesis String solution in Python
Additional Resources

678. Valid Parenthesis String LeetCode Solution image

Problem Statement of Valid Parenthesis String

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.
The following rules define a valid string:

Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string “”.

Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “(*)”
Output: true
Example 3:
Input: s = “(*))”
Output: true

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

678. Valid Parenthesis String LeetCode Solution in C++

class Solution {
 public:
  bool checkValidString(const string& s) {
    int low = 0;   // the lower bound of the number of valid '('s
    int high = 0;  // the upper bound of the number of valid '('s

    for (const char c : s) {
      switch (c) {
        case '(':
          ++low;
          ++high;
          break;
        case ')':
          low = max(0, --low);
          --high;
          break;
        case '*':
          low = max(0, --low);
          ++high;
          break;
      }
      if (high < 0)
        return false;
    }

    return low == 0;
  }
};
/* code provided by PROGIEZ */

678. Valid Parenthesis String LeetCode Solution in Java

class Solution {
  public boolean checkValidString(final String s) {
    int low = 0;  // the lower bound of the number of valid '('s
    int high = 0; // the upper bound of the number of valid '('s

    for (final char c : s.toCharArray()) {
      switch (c) {
        case '(':
          ++low;
          ++high;
          break;
        case ')':
          low = Math.max(0, --low);
          --high;
          break;
        case '*':
          low = Math.max(0, --low);
          ++high;
          break;
      }
      if (high < 0)
        return false;
    }

    return low == 0;
  }
}
// code provided by PROGIEZ

678. Valid Parenthesis String LeetCode Solution in Python

class Solution:
  def checkValidString(self, s: str) -> bool:
    low = 0
    high = 0

    for c in s:
      if c == '(':
        low += 1
        high += 1
      elif c == ')':
        if low > 0:
          low -= 1
        high -= 1
      else:
        if low > 0:
          low -= 1
        high += 1
      if high < 0:
        return False

    return low == 0
 # code by PROGIEZ