Valid Parenthesis String

MEDIUM

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

Approaches

Checkout 4 different approaches to solve Valid Parenthesis String. Click on different approaches to view the approach and algorithm in detail.

Brute Force using Recursion

This approach explores every possible interpretation of the '' characters. For each '', we recursively try three possibilities: treating it as an opening parenthesis '(', a closing parenthesis ')', or an empty string. This exhaustive search checks if any combination results in a valid parenthesis string.

Algorithm

Define a recursive function check(s, index, openCount).
index is the current position in the string, and openCount is the balance of open parentheses.
Base Case 1: If openCount becomes negative, it's an invalid state, return false.
Base Case 2: If index reaches the end of the string, the string is valid if and only if openCount is 0.
Recursive Step:
- If s[index] is '(', recurse with check(s, index + 1, openCount + 1).
- If s[index] is ')', recurse with check(s, index + 1, openCount - 1).
- If s[index] is '*', explore all three possibilities by making three separate recursive calls:
  1. Treat * as '(': check(s, index + 1, openCount + 1).
  2. Treat * as ')': check(s, index + 1, openCount - 1).
  3. Treat * as empty: check(s, index + 1, openCount).
- Return true if any of the three branches for * return true.

We define a recursive function check(index, open_count) which determines if the substring starting from index is valid, given a current balance of open_count open parentheses.

The base case for the recursion is when we reach the end of the string (index == s.length()). The string is valid if and only if the open_count is zero.
Another base case is if open_count ever becomes negative, which means we have an invalid sequence (e.g., a ')' without a preceding '('). In this case, we prune the search path by returning false.
In the recursive step, for the character at the current index:
- If it's '(', we increment open_count and recurse on the next index.
- If it's ')', we decrement open_count and recurse.
- If it's '*', we branch out and make three recursive calls: one for treating it as '(', one for ')', and one for an empty string. If any of these branches return true, the string is valid.

class Solution {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }

    private boolean check(String s, int index, int openCount) {
        if (openCount < 0) {
            return false;
        }
        if (index == s.length()) {
            return openCount == 0;
        }

        char c = s.charAt(index);
        if (c == '(') {
            return check(s, index + 1, openCount + 1);
        } else if (c == ')') {
            return check(s, index + 1, openCount - 1);
        } else { // c == '*'
            // Try all 3 possibilities for '*'
            return check(s, index + 1, openCount + 1) || // as '('
                   check(s, index + 1, openCount - 1) || // as ')'
                   check(s, index + 1, openCount);      // as empty
        }
    }
}

Complexity Analysis

Time Complexity: O(3^n), where n is the length of the string. In the worst case (a string of all '*'), we have 3 choices for each character, leading to an exponential number of paths.Space Complexity: O(n), for the recursion stack depth, where n is the length of the string.

Pros and Cons

Pros:

Simple to understand and implement the core logic.
Correctly explores all possibilities.

Cons:

Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.

Code Solutions

Checking out 3 solutions in different languages for Valid Parenthesis String. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Valid Parenthesis String

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

StringStack

Companies:

ServiceNow |Tekion |Alibaba |Roku |