678. Valid Parenthesis String

1. 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 “”.

2. Example

Example 1

Input: s = “()”
Output: true

Example 2

Input: s = “(*)”
Output: true

Example 3

Input: s = “(*))”
Output: true

3. Constraints

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

4. Solutions

Greedy

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    bool checkValidString(const string &str) {
        int max_balance = 0, min_balance = 0;
        for (char c : str) {
            if (c == '(') {
                ++max_balance;
                ++min_balance;
            } else if (c == ')') {
                --max_balance;
                --min_balance;
            } else {
                ++max_balance;
                --min_balance;
            }

            if (max_balance < 0) {
                return false;
            }

            min_balance = max(min_balance, 0);
        }

        return min_balance == 0;
    }
};