## 678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis `'('` must have a corresponding right parenthesis `')'`.
2. Any right parenthesis `')'` must have a corresponding left parenthesis `'('`.
3. Left parenthesis `'('` must go before the corresponding right parenthesis `')'`.
4. `'*'` could be treated as a single right parenthesis `')'` or a single left parenthesis `'('` or an empty string.
5. An empty string is also valid.

Example 1:

```Input: "()"
Output: True
```

Example 2:

```Input: "(*)"
Output: True
```

Example 3:

```Input: "(*))"
Output: True
```

Note:

1. The string size will be in the range [1, 100].

b'
\n\n

#### Approach #1: Brute Force [Time Limit Exceeded]

\n

Intuition and Algorithm

\n

For each asterisk, let\'s try both possibilities.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of the string. For each asterisk we try 3 different values. Thus, we could be checking the validity of up to strings. Then, each check of validity is .

\n
• \n
• \n

Space Complexity: , the space used by our character array.

\n
• \n
\n
\n

#### Approach #2: Dynamic Programming [Accepted]

\n

Intuition and Algorithm

\n

Let `dp[i][j]` be `true` if and only if the interval `s[i], s[i+1], ..., s[j]` can be made valid. Then `dp[i][j]` is true only if:

\n
\n
• \n

`s[i]` is `\'*\'`, and the interval `s[i+1], s[i+2], ..., s[j]` can be made valid;

\n
• \n
• \n

or, `s[i]` can be made to be `\'(\'`, and there is some `k` in `[i+1, j]` such that `s[k]` can be made to be `\')\'`, plus the two intervals cut by `s[k]` (`s[i+1: k]` and `s[k+1: j+1]`) can be made valid;

\n
• \n
\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of the string. There are states corresponding to entries of `dp`, and we do an average of work on each state.

\n
• \n
• \n

Space Complexity: , the space used to store intermediate results in `dp`.

\n
• \n
\n
\n

#### Approach #3: Greedy [Accepted]

\n

Intuition

\n

When checking whether the string is valid, we only cared about the "`balance`": the number of extra, open left brackets as we parsed through the string. For example, when checking whether \'(()())\' is valid, we had a balance of `1, 2, 1, 2, 1, 0` as we parse through the string: `\'(\'` has 1 left bracket, `\'((\'` has 2, `\'(()\'` has 1, and so on. This means that after parsing the first `i` symbols, (which may include asterisks,) we only need to keep track of what the `balance` could be.

\n

For example, if we have string `\'(***)\'`, then as we parse each symbol, the set of possible values for the `balance` is `` for `\'(\'`; `[0, 1, 2]` for `\'(*\'`; `[0, 1, 2, 3]` for `\'(**\'`; `[0, 1, 2, 3, 4]` for `\'(***\'`, and `[0, 1, 2, 3]` for `\'(***)\'`.

\n

Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as `[lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3]`.

\n

Algorithm

\n

Let `lo, hi` respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

\n

If we encounter a left bracket (`c == \'(\'`), then `lo++`, otherwise we could write a right bracket, so `lo--`. If we encounter what can be a left bracket (`c != \')\'`), then `hi++`, otherwise we must write a right bracket, so `hi--`. If `hi < 0`, then the current prefix can\'t be made valid no matter what our choices are. Also, we can never have less than `0` open left brackets. At the end, we should check that we can have exactly 0 open left brackets.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of the string. We iterate through the string once.

\n
• \n
• \n

Space Complexity: , the space used by our `lo` and `hi` pointers. However, creating a new character array will take space.

\n
• \n
\n
\n

Analysis written by: @awice

\n
'