LeetCode 678 - Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/description/

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

X.
http://www.cnblogs.com/grandyang/p/7617017.html
既然星号可以当左括号和右括号，那么我们就正反各遍历一次，正向遍历的时候，我们把星号都当成左括号，此时用经典的验证括号的方法，即遇左括号计数器加1，遇右括号则自减1，如果中间某个时刻计数器小于0了，直接返回false。如果最终计数器等于0了，我们直接返回true，因为此时我们把星号都当作了左括号，可以跟所有的右括号抵消。而此时就算计数器大于0了，我们暂时不能返回false，因为有可能多余的左括号是星号变的，星号也可以表示空，所以有可能不多，我们还需要反向q一下，哦不，是反向遍历一下，这是我们将所有的星号当作右括号，遇右括号计数器加1，遇左括号则自减1，如果中间某个时刻计数器小于0了，直接返回false。遍历结束后直接返回true，这是为啥呢？此时计数器有两种情况，要么为0，要么大于0。为0不用说，肯定是true，为啥大于0也是true呢？因为之前正向遍历的时候，我们的左括号多了，我们之前说过了，多余的左括号可能是星号变的，也可能是本身就多的左括号。本身就多的左括号这种情况会在反向遍历时被检测出来，如果没有检测出来，说明多余的左括号一定是星号变的。而这些星号在反向遍历时又变做了右括号，最终导致了右括号有剩余，所以当这些星号都当作空的时候，左右括号都是对应的，即是合法的。你可能会有疑问，右括号本身不会多么，其实不会的，如果多的话，会在正向遍历中被检测出来
https://leetcode.com/problems/valid-parenthesis-string/discuss/139759/Java-Very-easy-solution.-No-recursion-or-dp.

Think this might be logically easiest solution for this problem.
Check from left to right and then check from right to left.
When check from left to right, take all '*'s as '(', to see whether can match all ')'s.
And, When check from right to left, take all '*'s as ')', to see whether can match all '('s.
If both checks are valid, then the string is valid.
p.s. Thanks to @vagnihotri1117, we can return true if the first check returns bal=0.

 public boolean checkValidString(String s) {
        int bal = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '*') bal++;
            else if (bal-- == 0) return false;
        }
        if (bal == 0) return true;
        bal = 0;
        for (int i = s.length()-1; i >= 0; i--) {
            if (s.charAt(i) == ')' || s.charAt(i) == '*') bal++;
            else if (bal-- == 0) return false;
        }
        return true;
    }

https://leetcode.com/problems/valid-parenthesis-string/discuss/107581/O(n)-time-O(1)-space-no-Recursion-just-scan-from-left-and-then-scan-from-right
https://leetcode.com/problems/valid-parenthesis-string/discuss/107589/Java-O(n)-2pass-ez-to-understand

It's truly easy to understand because we just need to record the number of '(', ')' and wildcard to see if wildcard can be '(' or ')'.

    public boolean checkFromLeft(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int star = 0;
        int open = 0;
        int close = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                open++;
            } else if (c == ')') {
                close++;
            } else {
                star++;
            }
            if (close > open + star) {
                return false;
            }
        }
        if (close == open || close - open <= star) {
            return true;
        }
        return false;
    }
    public boolean checkFromRight(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int star = 0;
        int open = 0;
        int close = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == ')') {
                open++;
            } else if (c == '(') {
                close++;
            } else {
                star++;
            }
            if (close > open + star) {
                return false;
            }
        }
        if (close == open || close - open <= star) {
            return true;
        }
        return false;
    }
    public boolean checkValidString(String s) {
        return checkFromLeft(s) && checkFromRight(s);
    }

public boolean checkValidString(String s) {

char[] array = s.toCharArray();

return scanFromLeft(array) && scanFromRight(array);

}

private boolean scanFromRight(char[] array) {

int right = 0, star = 0;

for (int i = array.length - 1; i >= 0; i--) {

char ch = array[i];

if (ch == ')') {

right++;

} else if (ch == '*') {

star++;

} else {

if (right > 0)

right--;

else if (star > 0)

star--;

else

return false;

}

}

return right <= star;

}

// valid or not

private boolean scanFromLeft(char[] array) {

int left = 0, star = 0;

for (char ch : array) {

if (ch == '(') {

left++;

} else if (ch == '*') {

star++;

} else {

if (left > 0)

left--;

else if (star > 0)

star--;

else

return false;

}

}

return left <= star;

}

X.
如果不存在星号，那么这题是不是异常的简单，我们甚至连stack都可以不用，直接用一个变量，遇到左括号，自增1，遇到右括号，如果此时计数器已经为0了，直接返回false，否则自减1，一旦计数器出现了负数，立即返回false，最后还要看变量是否为0即可。但是由于星号的存在，这道题就变的复杂了，由于星号可以当括号用，所以当遇到右括号时，就算此时变量为0，也可以用星号来当左括号使用。那么星号什么时候都能当括号来用吗，我们来看两个例子 *) 和 *( ，在第一种情况下，星号可以当左括号来用，而在第二种情况下，无论星号当左括号，右括号，还是空，*( 都是不对的。当然这种情况只限于星号和左括号之间的位置关系，而只要星号在右括号前面，就一定可以消掉右括号。那么我们使用两个stack，分别存放左括号和星号的位置，遍历字符串，当遇到星号时，压入星号栈star，当遇到左括号时，压入左括号栈left，当遇到右括号时，此时如果left和star均为空时，直接返回false；如果left不为空，则pop一个左括号来抵消当前的右括号；否则从star中取出一个星号当作左括号来抵消右括号。当循环结束后，我们希望left中没有多余的左括号，就算有，我们可以尝试着用星号来抵消，当star和left均不为空时，进行循环，如果left的栈顶左括号的位置在star的栈顶星号的右边，那么就组成了 *( 模式，直接返回false；否则就说明星号可以抵消左括号，各自pop一个元素。最终退出循环后我们看left中是否还有多余的左括号，没有就返回true，否则false

    bool checkValidString(string s) {
        stack<int> left, star;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '*') star.push(i);
            else if (s[i] == '(') left.push(i);
            else {
                if (left.empty() && star.empty()) return false;
                if (!left.empty()) left.pop();
                else star.pop();
            }
        }
        while (!left.empty() && !star.empty()) {
            if (left.top() > star.top()) return false;
            left.pop(); star.pop();
        }
        return left.empty();
    }

https://leetcode.com/problems/valid-parenthesis-string/discuss/107572/Java-using-2-stacks.-O(n)-space-and-time-complexity.

The basic idea is to track the index of the left bracket and star position.
Push all the indices of the star and left bracket to their stack respectively.
STEP 1
Once a right bracket comes, pop left bracket stack first if it is not empty. If the left bracket stack is empty, pop the star stack if it is not empty. A false return can be made provided that both stacks are empty.

STEP 2
Now attention is paid to the remaining stuff in these two stacks. Note that the left bracket CANNOT appear after the star as there is NO way to balance the bracket. In other words, whenever there is a left bracket index appears after the Last star, a false statement can be made. Otherwise, pop out each from the left bracket and star stack.

STEP 3
A correct sequence should have an empty left bracket stack. You don't need to take care of the star stack.

Final Remarks:
Greedy algorithm is used here. We always want to use left brackets to balance the right one first as the * symbol is a wild card. There is probably an O(1) space complexity but I think this is worth mentioning.

    public boolean checkValidString(String s) {
        Stack<Integer> leftID = new Stack<>();
        Stack<Integer> starID = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(')
                leftID.push(i);
            else if (ch == '*')
                starID.push(i);
            else {
                if (leftID.isEmpty() && starID.isEmpty())   return false;
                if (!leftID.isEmpty())
                    leftID.pop();
                else 
                    starID.pop();
            }
        }
        while (!leftID.isEmpty() && !starID.isEmpty()) {
            if (leftID.pop() > starID.pop()) 
                return false;
        }
        return leftID.isEmpty();
    }

X. Greedy

这里维护了两个变量low和high，其中low表示在有左括号的情况下，将星号当作右括号时左括号的个数(这样做的原因是尽量不多增加右括号的个数)，而high表示将星号当作左括号时左括号的个数。是不是很绕，没办法。那么当high小于0时，说明就算把星号都当作左括号了，还是不够抵消右括号，返回false。而当low大于0时，说明左括号的个数太多了，没有足够多的右括号来抵消，返回false。那么开始遍历字符串，当遇到左括号时，low和high都自增1；当遇到右括号时，只有当low大于0时，low才自减1，保证了low不会小于0，而high直接自减1；当遇到星号时，只有当low大于0时，low才自减1，保证了low不会小于0，而high直接自增1，因为high把星号当作左括号。当此时high小于0，说明右括号太多，返回false。当循环退出后，我们看low是否为0
https://leetcode.com/problems/valid-parenthesis-string/discuss/107611/Very-concise-C%2B%2B-solution-with-explaination.-No-DP

Since * can be used as 3 kinds of char, if we do backtrack the complexity can blow up if the string is *****.... We need to find a non-trivial method.
Without *, we can just use a number to indicate the unmatch (, ( will increment it and ) will decrement it. We don't want this number less than 0 all the time and it should be 0 when all the string has been matched.
When * is introduced, the number becomes a range, indicating the number of possible unmatched ( found. One * just expand the range by 1. And we can use the same principle to check if the criteria above is within the range.

    bool checkValidString(string s) {
        int lower = 0, upper = 0;
        for (char c : s) {
            if (c=='(') {
                lower++;
                upper++;
            } else if (c==')') {
                lower--;               
                upper--;
            } else { // * encountered
                lower--;
                upper++;
            }
            lower = max(lower, 0);
            if (upper<0) // unmatched ')' found in the middle of string
                return false;
        }
        return lower==0;
    }

https://leetcode.com/problems/valid-parenthesis-string/discuss/107577/Short-Java-O(n)-time-O(1)-space-one-pass

The idea is to similar to validate a string only contains '(' and ')'. But extend it to tracking the lower and upper bound of valid '(' counts. My thinking process is as following.

scan from left to right, and record counts of unpaired ‘(’ for all possible cases. For ‘(’ and ‘)’, it is straightforward, just increment and decrement all counts, respectively.
When the character is '*', there are three cases, ‘(’, empty, or ‘)’, we can think those three cases as three branches in the ongoing route.
Take “(**())” as an example. There are 6 chars:
----At step 0: only one count = 1.
----At step 1: the route will be diverted into three branches.
so there are three counts: 1 - 1, 1, 1 + 1 which is 0, 1, 2, for ‘)’, empty and ‘(’ respectively.
----At step 2 each route is diverged into three routes again. so there will be 9 possible routes now.
-- For count = 0, it will be diverted into 0 – 1, 0, 0 + 1, which is -1, 0, 1, but when the count is -1, that means there are more ‘)’s than ‘(’s, and we need to stop early at that route, since it is invalid. we end with 0, 1.
-- For count = 1, it will be diverted into 1 – 1, 1, 1 + 1, which is 0, 1, 2
-- For count = 2, it will be diverted into 2 – 1, 2, 2 + 1, which is 1, 2, 3
To summarize step 2, we end up with counts of 0,1,2,3
----At step 3, increment all counts --> 1,2,3,4
----At step 4, decrement all counts --> 0,1,2,3
----At step 5, decrement all counts --> -1, 0,1,2, the route with count -1 is invalid, so stop early at that route. Now we have 0,1,2.
In the very end, we find that there is a route that can reach count == 0. Which means all ‘(’ and ‘)’ are cancelled. So, the original String is valid.
Another finding is counts of unpaired ‘(’ for all valid routes are consecutive integers. So we only need to keep a lower and upper bound of that consecutive integers to save space.
One case doesn’t show up in the example is: if the upper bound is negative, that means all routes have more ‘)’ than ‘(’ --> all routes are invalid --> stop and return false

    public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                low++;
                high++;
            } else if (s.charAt(i) == ')') {
                if (low > 0) {
                    low--;
                }
                high--;
            } else {
                if (low > 0) {
                    low--;
                }
                high++;
            }
            if (high < 0) {
                return false;
            }
        }
        return low == 0;
    }

https://leetcode.com/problems/valid-parenthesis-string/discuss/107611/Very-concise-C++-solution-with-explaination.-No-DP
https://leetcode.com/problems/valid-parenthesis-string/discuss/107577/Short-Java-O(n)-time-O(1)-space-one-pass

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 

    public boolean checkValidString(String s) {
       int lo = 0, hi = 0;
       for (char c: s.toCharArray()) {
           lo += c == '(' ? 1 : -1;
           hi += c != ')' ? 1 : -1;
           if (hi < 0) break;
           lo = Math.max(lo, 0);
       }
       return lo == 0;
    }

X. DP
https://leetcode.com/problems/valid-parenthesis-string/solution/

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;

• Time Complexity: $O(N^3)$, where $N$ is the length of the string. There are $O(N^2)$ states corresponding to entries of dp, and we do an average of $O(N)$ work on each state.
• Space Complexity: $O(N^2)$, the space used to store intermediate results in dp.

    public boolean checkValidString(String s) {
        int n = s.length();
        if (n == 0) return true;
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') dp[i][i] = true;
            if (i < n-1 &&
                    (s.charAt(i) == '(' || s.charAt(i) == '*') &&
                    (s.charAt(i+1) == ')' || s.charAt(i+1) == '*')) {
                dp[i][i+1] = true;
            }
        }

        for (int size = 2; size < n; size++) {
            for (int i = 0; i + size < n; i++) {
                if (s.charAt(i) == '*' && dp[i+1][i+size] == true) {
                    dp[i][i+size] = true;
                } else if (s.charAt(i) == '(' || s.charAt(i) == '*') {
                    for (int k = i+1; k <= i+size; k++) {
                        if ((s.charAt(k) == ')' || s.charAt(k) == '*') &&
                                (k == i+1 || dp[i+1][k-1]) &&
                                (k == i+size || dp[k+1][i+size])) {
                            dp[i][i+size] = true;
                        }
                    }
                }
            }
        }
        return dp[0][n-1];
    }

X. DFS + cache
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-678-valid-parenthesis-string/

    bool checkValidString(const string& s) {

        int l = s.length();

        m_ = vector<vector<int>>(l, vector<int>(l, -1));

        return isValid(s, 0, l - 1);

    }

private:

    vector<vector<int>> m_;

    bool isValid(const string& s, int i, int j) {

        if (i > j) return true;

        if (m_[i][j] >= 0) return m_[i][j];        

        

        if (i == j) return m_[i][j] = (s[i] == '*');

        

        if ((s[i] == '(' || s[i] == '*')

          &&(s[j] == ')' || s[j] == '*')

          && isValid(s, i + 1, j - 1))

                return m_[i][j] = 1;        

        

        for (int p = i; p < j; ++p)

            if (isValid(s, i, p) && isValid(s, p + 1, j))

                return m_[i][j] = 1;                        

        

        return m_[i][j] = 0;

    }

X. Brute Force
感觉应该属于暴力破解法。使用了变量cnt来记录左括号的个数，变量start表示当前开始遍历的位置，那么在递归函数中，首先判断如果cnt小于0，直接返回false。否则进行从start开始的遍历，如果当前字符为左括号，cnt自增1；如果为右括号，若cnt此时小于等于0，返回false，否则cnt自减1；如果为星号，我们同时递归三种情况，分别是当星号为空，左括号，或右括号，只要有一种情况返回true，那么就是true了。如果循环退出后，若cnt为0，返回true，否则false
https://leetcode.com/problems/valid-parenthesis-string/discuss/107566/Java-12-lines-solution-backtracking

1. How to check valid parenthesis w/ only ( and )? Easy. Count each char from left to right. When we see (, count++; when we see ) count--; if count < 0, it is invalid () is more than (); At last, count should == 0.
2. This problem added *. The easiest way is to try 3 possible ways when we see it. Return true if one of them is valid.

class Solution {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }
    
    private boolean check(String s, int start, int count) {
        if (count < 0) return false;
        
        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            }
            else if (c == ')') {
                if (count <= 0) return false;
                count--;
            }
            else if (c == '*') {
                return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
            }
        }
        
        return count == 0;
    }

For each asterisk, let's try both possibilities.

• Time Complexity: $O(N * 3^{N})$, where $N$ is the length of the string. For each asterisk we try 3 different values. Thus, we could be checking the validity of up to $3^N$ strings. Then, each check of validity is $O(N)$.
• Space Complexity: $O(N)$, the space used by our character array.

    boolean ans = false;

    public boolean checkValidString(String s) {
        solve(new StringBuilder(s), 0);
        return ans;
    }

    public void solve(StringBuilder sb, int i) {
        if (i == sb.length()) {
            ans |= valid(sb);
        } else if (sb.charAt(i) == '*') {
            for (char c: "() ".toCharArray()) {
                sb.setCharAt(i, c);
                solve(sb, i+1);
                if (ans) return;
            }
            sb.setCharAt(i, '*');
        } else
            solve(sb, i + 1);
    }

    public boolean valid(StringBuilder sb) {
        int bal = 0;
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (c == '(') bal++;
            if (c == ')') bal--;
            if (bal < 0) break;
        }
        return bal == 0;
    }
https://leetcode.com/problems/valid-parenthesis-string/discuss/107566/Java-12-lines-solution-backtracking

1. How to check valid parenthesis w/ only ( and )? Easy. Count each char from left to right. When we see (, count++; when we see ) count--; if count < 0, it is invalid () is more than (); At last, count should == 0.
2. This problem added *. The easiest way is to try 3 possible ways when we see it. Return true if one of them is valid.

    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }
    
    private boolean check(String s, int start, int count) {
        if (count < 0) return false;
        
        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            }
            else if (c == ')') {
                if (count <= 0) return false;
                count--;
            }
            else if (c == '*') {
                return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
            }
        }
        
        return count == 0;
    }

X. https://leetcode.com/articles/valid-parenthesis-string/

For each asterisk, let's try both possibilities.

Time Complexity: $O(N * 3^{N})$, where $N$ is the length of the string. For each asterisk we try 3 different values. Thus, we could be checking the validity of up to $3^N$ strings. Then, each check of validity is $O(N)$.

  boolean ans = false;

  public boolean checkValidString(String s) {

    solve(new StringBuilder(s), 0);

    return ans;

  }

  public void solve(StringBuilder sb, int i) {

    if (i == sb.length()) {

      ans |= valid(sb);

    } else if (sb.charAt(i) == '*') {

      for (char c : "() ".toCharArray()) {

        sb.setCharAt(i, c);

        solve(sb, i + 1);

        if (ans)

          return;

      }

      sb.setCharAt(i, '*');

    } else

      solve(sb, i + 1);

  }

  public boolean valid(StringBuilder sb) {

    int bal = 0;

    for (int i = 0; i < sb.length(); i++) {

      char c = sb.charAt(i);

      if (c == '(')

        bal++;

      if (c == ')')

        bal--;

      if (bal < 0)

        break;

    }

    return bal == 0;

  }

http://bookshadow.com/weblog/2017/09/17/leetcode-valid-parenthesis-string/

遍历s中的字符c，利用集合vset记录所有当前左括号-右括号的差值

  若c == '('，将vset替换为其所有元素+1

  若c == ')'，将vset替换为其所有不小于1的元素 - 1

  若c == '*’，将vset中的所有元素+1，-1后，保留非负元素

遍历结束，判断vset中是否包含0元素

https://blog.csdn.net/fuxuemingzhu/article/details/80680990

这个思路是这样的：用一个set集合来记录这个表达式中左括号能比右括号多的个数。注意，是能够。因此，如果遇到左括号，集合里面的每个元素应该+1；遇到右括号，如果集合里边的>0的元素可以-1；如果遇到*，应该+1，-1或者不运算。看最后这个集合能否包含0，即左括号的个数等于右括号的个数。

那这个算法怎么判断的”)(“呢？巧妙的地方就在于，只有set里面大于0的元素才去-1；因此刚开始set只有0元素，所以)不算数。所以这个方法真的很巧妙

def checkValidString(self, s): """ :type s: str :rtype: bool """ vset = set([0]) for c in s: nset = set() if c == '*': for v in vset: nset.add(v + 1) nset.add(v) if v >= 1: nset.add(v - 1) elif c == '(': for v in vset: nset.add(v + 1) elif c == ')': for v in vset: if v >= 1: nset.add(v - 1) vset = nset return 0 in vset