LeetCode678. Valid Parenthesis String

今天药忘吃喽~ 2022-06-06 23:22 115阅读 0赞

# Analysis #

## Solution1 ##

The idea is to use an int `count` to keep tracking the relationship between left parenthesis and right parenthesis since we don’t care about the exact parenthesis but rather their corresponding counts.

For every character in the input `String s`, there are 3 possible conditions:

1.  Current character is `'('`, then we increase the `count`.
2.  Current character is `')'`, then we decrease the `count`.
3.  Current character is `'*'`, there are 3 possible sub-conditions:
    
     *  Treat `*` as `(`, increase `count` by 1.
     *  Treat `*` as `)`, decrease `count` by 1.
     *  Treat `*` as empty string, count does not change.

### Complexity ###

The space complexity of this solution is `O(1)` without considering the recursion stack. The recursion stack space would be linear to the length of the input String.

The time complexity would be `O(n)` as well. Worst case `O(2^n)` to `O(3^n)` when the input string contains only `*`.

Suppose `n` is the length of the input string.

Then we have the following solution based on straight-forwardly implement the above thoughts.

class Solution {
        
        public boolean checkValidString(String s) {
            if (s == null || s.isEmpty() || s.length() == 0) {
                return true;
            }
    
            char[] charS = s.toCharArray();
            return checkValidStringHelper(charS, 0, 0);
        }
    
        private boolean checkValidStringHelper(char[] charS, int start, int count) {
            // Base case
            if (start == charS.length) {
                return count == 0 ? true : false;
            }
    
            // If the count smaller than 0, early stop cause this is invalid.
            if (count < 0) {
                return false;
            }
    
            if (charS[start] == '(') {
                return checkValidStringHelper(charS, start + 1, count + 1);
            } else if (charS[start] == ')') {
                return checkValidStringHelper(charS, start + 1, count - 1);
            } else { // charS[start] == '*'
                // 1. treat '*' as empty string
                boolean ret1 = checkValidStringHelper(charS, start + 1, count);
                // 2. treat '*' as left parenthesis
                boolean ret2 = checkValidStringHelper(charS, start + 1, count + 1);
                // 3. treat '*' as right parenthesis
                boolean ret3 = checkValidStringHelper(charS, start + 1, count - 1);
    
                return (ret1 || ret2 || ret3);
            }
        }
    }

## Solution2 (More optimal) ##

Another interesting observation is that the resulting count will actually be a continuous sequence of integer.

E.g., for input `"(**))"`

At step 1, the count would be 1.

At step 2, the count would be 0, 1, or 2

At step 3, the count would be `0+1, 0, 0-1, 1+1, 1, 1-1, 2+1, 2, 2-1`, which is `-1, 0, 1, 2, 3`. And since negative count is always invalid, we early stop for these conditions. ==> `0, 1, 2, 3`.

At step 4, the count would be `0, 1, 2` with early pruning.

At step 5, the count would be `0, 1` with early pruning.

Considering that actually the reslut count is a consecutive sequence of integers, we can actually stores only the range of the output rather than iterate through all possible conditions.

### Complexity ###

This algorithm runs in `O(1)` space and `O(n)` time where `n` is the length of the input string.

Resulting to the following solution:

class Solution {
        public boolean checkValidString(String s) {
            if (s == null || s.isEmpty() || s.length() == 0) {
                return true;
            }
    
            int low = 0;
            int high = 0;
            for (char c : s.toCharArray()) {
                if (c == '(') {
                    high++;
                    low++;
                } else if (c == ')') {
                    if (low > 0) {
                        low--;
                    }
                    high--;
                } else { //c == '*'
                    if (low > 0) {
                        low--;
                    }
                    high++;
                }
    
                if (high < 0) {
                    return false;
                }
            }
    
            // Since we have pruned all conditions where low is smaller than 0, the smallest low would be 0
            // if the input string is valid.
            return low == 0;
        }
    }