Formatted question description: https://leetcode.ca/all/678.html

678. Valid Parenthesis String (Medium)

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

Companies:
Facebook, Amazon, Bloomberg

Related Topics:
String

Similar Questions:

Solution 1.

This solution is not performant if s contains lots of "*".

// OJ: https://leetcode.com/problems/valid-parenthesis-string/
// Time: O(3^S) where S is the length of string s. In the worst case every character
//       is "*", so every step has 3 choices.
// Space: O(S)
class Solution {
private:
    bool dfs(string &s, int start, int leftParenCnt) {
        if (start == s.size()) return !leftParenCnt;
        if (s[start] == '(') {
            return dfs(s, start + 1, leftParenCnt + 1);
        } else if (s[start] == ')') {
            if (--leftParenCnt < 0) return false;
            return dfs(s, start + 1, leftParenCnt);
        } else {
            if (dfs(s, start + 1, leftParenCnt + 1)) return true;
            if (leftParenCnt >= 1 && dfs(s, start + 1, leftParenCnt - 1)) return true;
            return dfs(s, start + 1, leftParenCnt);
        }
    }
public:
    bool checkValidString(string s) {
        return dfs(s, 0, 0);
    }
};

Solution 2.

Let diff be count of left parenthesis minus count of right parenthesis.

When we meet:

  • (, we increment diff.
  • ), we decrement diff.
  • *, we have three choices which makes the diff become a range – [diff - 1, diff + 1].

So we use maxDiff/minDiff to record the maximum/minimum diff we can get.

When we meet:

  • (, ++maxDiff and ++minDiff.
  • ), --maxDiff and --minDiff.
  • *, ++maxDiff and --minDiff.

If maxDiff become negative, it means it’s already invalid, we should return false.

Whenever minDiff falls below 0, we should force it to be 0 because we never accept negative diff during the process.

After scanning through string s, as long as minDiff is 0, this string can be a valid one.

Whenever minDiff falls below 0, we should force it to be 0 because we never accept negative diff during the process.

minDiff means the diff we got if we always try to replace * with ). If minDiff become -1, it means that this replacement results in more ) than (, so it should be avoided. To avoid it, we simply reset minDiff from -1 to 0 which implies we only replace * with ( or empty string.

Example: (**)

  • Seeing (, the range becomes [1, 1].
  • Seeing *, the range becomes [0, 2]. 0 correponds to (), 1 to (_, 2 to ((.
  • Seeing *, the range becomes [-1,3]. But -1 is invalid because it means ()) and should be avoided. So we correct the range to [0, 3].
  • Seeing ), the range becomes [-1, 2]. Again, we correct the range to [0, 2] (because -1 means ()_) or (_)))

The final [0, 2] range means that we can either get a perfect string, or has 1 or 2 more ( available (which are created by *).

// OJ: https://leetcode.com/problems/valid-parenthesis-string/
// Time: O(S)
// Space: O(1)
class Solution {
public:
    bool checkValidString(string s) {
        int maxDiff = 0, minDiff = 0;
        for (char c : s) {
            maxDiff += (c == '(' || c == '*') ? 1 : -1;
            minDiff += (c == ')' || c == '*') ? -1 : 1;
            if (maxDiff < 0) return false;
            minDiff = max(0, minDiff);
        }
        return minDiff == 0;
    }
};

Java

  • class Solution {
        public boolean checkValidString(String s) {
            Stack<Integer> parenthesesStack = new Stack<Integer>();
            Queue<Integer> asterisksQueue = new LinkedList<Integer>();
            int length = s.length();
            for (int i = 0; i < length; i++) {
                char c = s.charAt(i);
                if (c == '*')
                    asterisksQueue.offer(i);
                else if (c == '(')
                    parenthesesStack.push(i);
                else if (c == ')') {
                    if (!parenthesesStack.isEmpty())
                        parenthesesStack.pop();
                    else if (!asterisksQueue.isEmpty())
                        asterisksQueue.poll();
                    else
                        return false;
                }
            }
            if (parenthesesStack.isEmpty())
                return true;
            else {
                Stack<Integer> newParenthesesStack = new Stack<Integer>();
            	while (!parenthesesStack.isEmpty())
            		newParenthesesStack.push(parenthesesStack.pop());
                while (!newParenthesesStack.isEmpty() && !asterisksQueue.isEmpty()) {
                    int parenthesisIndex = newParenthesesStack.peek();
                    int asteriskIndex = asterisksQueue.poll();
                    if (parenthesisIndex < asteriskIndex)
                    	newParenthesesStack.pop();
                }
                return newParenthesesStack.isEmpty();
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/valid-parenthesis-string/
    // Time: O(3^S) where S is the length of string s. In the worst case every character
    //       is "*", so every step has 3 choices.
    // Space: O(S)
    class Solution {
    private:
        bool dfs(string &s, int start, int leftParenCnt) {
            if (start == s.size()) return !leftParenCnt;
            if (s[start] == '(') {
                return dfs(s, start + 1, leftParenCnt + 1);
            } else if (s[start] == ')') {
                if (--leftParenCnt < 0) return false;
                return dfs(s, start + 1, leftParenCnt);
            } else {
                if (dfs(s, start + 1, leftParenCnt + 1)) return true;
                if (leftParenCnt >= 1 && dfs(s, start + 1, leftParenCnt - 1)) return true;
                return dfs(s, start + 1, leftParenCnt);
            }
        }
    public:
        bool checkValidString(string s) {
            return dfs(s, 0, 0);
        }
    };
    
  • class Solution(object):
        def checkValidString(self, s):
            """
            :type s: str
            :rtype: bool
            """
            old_set = set([0])
            for c in s:
                new_set = set()
                if c == '(':
                    for t in old_set:
                        new_set.add(t + 1)
                elif c == ')':
                    for t in old_set:
                        if t > 0:
                            new_set.add(t - 1)
                elif c == '*':
                    for t in old_set:
                        new_set.add(t + 1)
                        new_set.add(t)
                        if t > 0:
                            new_set.add(t - 1)
                old_set = new_set
            return 0 in old_set
    

All Problems

All Solutions