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


Approach #1: Brute Force [Time Limit Exceeded]

Intuition and Algorithm

For each asterisk, let's try both possibilities.

Complexity Analysis

  • 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 .

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

Approach #2: Dynamic Programming [Accepted]

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:

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

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

Complexity Analysis

  • 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.

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

Approach #3: Greedy [Accepted]

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

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

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

Analysis written by: @awice

Submit Solution