678. Valid Parenthesis String

2020, Dec 05 2 mins read

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

Search

Tags