Skip to content

678. Valid Parenthesis String

Solve in Leetcode

Description

Static Badge

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

Solution: Greedy Approach

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

There are two conditions in which the string is unbalanced

  • We encounter too many ')'
  • In the end, we still have some '(' which didn't find their matching ')'
Why does we need openMin = Math.max(openMin, 0)?

openMin will be subtracted by 1, whenever we encounter either ')' or '*'. However, if we just ignore the '*' as empty strings. Eg,

Input: "()**" // openMin = 1 0 0 0
openMax = 1 0 1 2
openMin = 1 0 -1 -2

Both "() " and "()))" will be matched, but since we ignored empty string, "()))" will be the final result, which is not correct. Hence if we make openMin become 0, and it become nothing similar to '' empty string definition and neither '(' nor ')' will be added.12

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function checkValidString(s: string): boolean {
    const chars = Array.from(s);
    let openMin = 0;
    let openMax = 0;

    for(var i = 0; i < chars.length; i++) {
        if (chars[i] == "(") {
            openMin++;
            openMax++;
        } else if (chars[i] == ")") {
            openMin--;
            openMax--;
        } else if (chars[i] == "*") {
            openMin--; // assume it as ")", so open parentheses will less one
            openMax++;
        }
        if (openMax < 0) return false; // not enough open parentheses for paring eg. ")(" will throw `false`

        openMin = Math.max(openMin, 0) // if negative, we assumed that the "*" could be ""
    }

    return openMin == 0;
};

  1. Explanation 1 ↩

  2. Explanation 2 ↩