678. Valid Parenthesis String - Medium

前往題目

想法

• 想從單純合法括號衍生出加了*的解，但是不知道該怎麼處理

思路

1. 遇到左與右括號正常增減計數
2. 當遇到星號，紀錄其當成左括號與右括號的情況
3. 如果星號都當成左括號還是無法匹配右括號直接回傳false，因為右括號無法靠左括號與空白補救
4. 如果星號都當成右括號當無法匹配的時候，把右括號再變為左括號，因為左括號可以補救右括號
5. 最後回傳右括號計數器，如果是0就代表成功匹配，因為右括號計數器會盡可能的補救，遇到無法匹配會馬上補救，所以等於零的時候代表成功匹配

Code

class Solution {
    public boolean checkValidString(String s) {
        // Max number of unmatched left paren., try to use ( as it can
        // Min number of unmatched left paren., try to use ) as it can
        int leftMax = 0, leftMin = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                ++leftMax;
                ++leftMin;
            } else if (c == ')') {
                --leftMax;
                --leftMin;
            } else { // *
                ++leftMax; // use it as a left paren.
                --leftMin; // use it as a right paren.
            }

            // Use all left paren. as it can but still can't match
            if (leftMax < 0) return false;
            // Use it as right paren. but becomes invalid 
            // so use left paren. instead
            if (leftMin < 0) leftMin = 0;
        }

        return leftMin == 0;
    }
}

// Unfinished code
class Solution {
    public boolean checkValidString(String s) {
        int starCount = 0;
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '*') {
                ++starCount;
                continue;
            }

            if (stack.empty() && starCount == 0) return false;

            if (c == '(') {
                stack.push(c);
            } else if (c == ')' && !stack.empty()){ // ')'
                stack.pop();
            }
        }

        while (!stack.empty() )

        return true;
    }
}