30-Day LeetCoding Challenge Day 16: Valid Parenthesis String

Valid Parenthesis要問我們一個只含(、)、*的字串，是否為合格的含括號字串。其中 ’*’ 可以是 (、或)，甚至可以是「空」值。

又是一題medium，這一題說老實話挺難的。先說暴力解，因為 ’*’ 可能代表三種值，所以每遇到 * ，就有三條邏輯分支，真的想要暴力解的話，時間複雜度會到O(N * 3^n)，相當可怕，想都別想 XD

我們先來看看「沒有*」的世界長什麼樣子好了，反正閒著也是閒著…

什麼是Valid？一個Valid Parenthesis String應該有以下兩個特性：

1. 從頭開始走到底，‘(‘ 跟 ‘)’ 的數量一樣多
2. 走的過程中的任何時刻， ‘)’ 一定不可以比 ‘(’ 多

於題我們可以定義一個值 diff，讓它代表「左比右多多少」。接下來我們就順著String從頭開始走，只要遇到 ’(’ 就加一，遇到 ’)’ 就減一，但一旦過程中 diff 被減到 -1，就直接回 false，不用再走下去。如果順利走完，就看 diff 是否剛好為0 就好。

問題來了，我們還是得面對 ‘*’ 的狀況。來分析看看吧…

與左右括號不同，’*’ 可以是左括、右括，也可以是 「空」，在不同case下，其對 diff 的影響可以是加一、減一，或是不變。因此，diff變得不確定，但幸好他的變動還在一定範圍內。

於是，我們可以把diff拆成 diffMin 與 diffMax，分別記下diff在過程中可能變成的值的最大與最小範圍。如此一來，每個元件對 diff的變化也能整理出來了：

(：diffMin+1, diffMax+1

)：diffMin -1, diffMax-1

‘*’： diffMin-1, diffMax+1

一樣，過程中如果任何時刻發現diffMax <0，即代表這個String不可能是Valid，就可以跳出來了。

另外，如果diffMin < 0，代表我們可以乎略這個選項，因為我們不打算考慮invalid的 case，因此「最小可能diff」不會低於0。

於是我們好像解完了：

public class Solution {
    public boolean checkValidString(String s) {

        // Array, Greedy
        // diff: #lefts - #rights
        int minDiff = 0;
        int maxDiff = 0;

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

            if (c == '(') {
                minDiff++;
                maxDiff++;
            } else if (c == '*') {
                minDiff--;
                maxDiff++;
            } else { // c==')'
                minDiff--;
                maxDiff--;
            }

            if (0 > maxDiff) {
                return false;
            }

            minDiff = Math.max(0, minDiff);

        }

        return minDiff == 0;
    }
}

Happy Coding！