This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:

- 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.- An empty string is also valid.

**Example 1:**

Input:"()"Output:True

**Example 2:**

Input:"(*)"Output:True

**Example 3:**

Input:"(*))"Output:True

**Note:**

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

b'

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

\n

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

\n

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

\n

\n

'
\n\n

\n**Intuition and Algorithm**

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

\n\n**Complexity Analysis**

- \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

**Intuition and Algorithm**

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
or,

\n`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

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of the string. There are states corresponding to entries of

\n`dp`

, and we do an average of work on each state. \n - \n
Space Complexity: , the space used to store intermediate results in

\n`dp`

. \n

\n

**Intuition**

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.

For example, if we have string `\'(***)\'`

, then as we parse each symbol, the set of possible values for the `balance`

is `[1]`

for `\'(\'`

; `[0, 1, 2]`

for `\'(*\'`

; `[0, 1, 2, 3]`

for `\'(**\'`

; `[0, 1, 2, 3, 4]`

for `\'(***\'`

, and `[0, 1, 2, 3]`

for `\'(***)\'`

.

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]`

.

**Algorithm**

Let `lo, hi`

respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

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.

**Complexity Analysis**

- \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

\n`lo`

and`hi`

pointers. However, creating a new character array will take space. \n

\n

Analysis written by: @awice

\n