Welcome to Subscribe On Youtube

678. Valid Parenthesis String

Description

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 '*'.

Solutions

Solution 1: Dynamic Programming

Let dp[i][j] be true if and only if the interval s[i], s[i+1], ..., s[j] can be made valid. Then dp[i][j] is true only if:

• s[i] is '*', and the interval s[i+1], s[i+2], ..., s[j] can be made valid;

• or, s[i] can be made to be '(', and there is some k in [i+1, j] such that s[k] can be made to be ')', plus the two intervals cut by s[k] (s[i+1: k] and s[k+1: j+1]) can be made valid;

• Time Complexity: $O(n^3)$, where $n$ is the length of the string. There are $O(n^2)$ states corresponding to entries of dp, and we do an average of $O(n)$ work on each state.
• Space Complexity: $O(n^2)$.

Solution 2: Greedy

Scan twice, first from left to right to make sure that each of the closing brackets is matched successfully, and second from right to left to make sure that each of the opening brackets is matched successfully.

• Time Complexity: $O(n)$, where $n$ is the length of the string.
• Space Complexity: $O(1)$.

• Java
• C++
• Python
• Go

• class Solution {
      public boolean checkValidString(String s) {
          int x = 0;
          int n = s.length();
          for (int i = 0; i < n; ++i) {
              if (s.charAt(i) != ')') {
                  ++x;
              } else if (x > 0) {
                  --x;
              } else {
                  return false;
              }
          }
          x = 0;
          for (int i = n - 1; i >= 0; --i) {
              if (s.charAt(i) != '(') {
                  ++x;
              } else if (x > 0) {
                  --x;
              } else {
                  return false;
              }
          }
          return true;
      }
  }
  

• class Solution {
  public:
      bool checkValidString(string s) {
          int x = 0, n = s.size();
          for (int i = 0; i < n; ++i) {
              if (s[i] != ')') {
                  ++x;
              } else if (x) {
                  --x;
              } else {
                  return false;
              }
          }
          x = 0;
          for (int i = n - 1; i >= 0; --i) {
              if (s[i] != '(') {
                  ++x;
              } else if (x) {
                  --x;
              } else {
                  return false;
              }
          }
          return true;
      }
  };
  

• class Solution:
      def checkValidString(self, s: str) -> bool:
          x = 0
          for c in s:
              if c in '(*':
                  x += 1
              elif x:
                  x -= 1
              else:
                  return False
          x = 0
          for c in s[::-1]:
              if c in '*)':
                  x += 1
              elif x:
                  x -= 1
              else:
                  return False
          return True
  
  

• func checkValidString(s string) bool {
  	x := 0
  	for _, c := range s {
  		if c != ')' {
  			x++
  		} else if x > 0 {
  			x--
  		} else {
  			return false
  		}
  	}
  	x = 0
  	for i := len(s) - 1; i >= 0; i-- {
  		if s[i] != '(' {
  			x++
  		} else if x > 0 {
  			x--
  		} else {
  			return false
  		}
  	}
  	return true
  }
  

All Problems

All Solutions