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)

class Solution {
public:
    bool checkValidString(const string &str) {
        int min_left_parenthesis = 0, max_left_parenthesis = 0;
        for (auto letter : str) {
            if (letter == '(') {
                ++min_left_parenthesis;
                ++max_left_parenthesis;
            } else if (letter == '*') {
                ++max_left_parenthesis;
                --min_left_parenthesis;
            } else {
                --min_left_parenthesis;
                --max_left_parenthesis;
            }

            if (max_left_parenthesis < 0) {
                return false;
            }

            min_left_parenthesis = max(0, min_left_parenthesis);
        }

        return min_left_parenthesis == 0;
    }
};