[leetcode]20. Valid Parentheses

題目：20. Valid Parentheses
提示關鍵字：堆疊(stack)

堆疊(stack)：一種資料結構，放入和取出的出口都是同一個，想像成一個裝書的紙箱，只能從上方放書與取書，由於最後放入的在最上方，照順序取出的第一本會是最後一本放入的書。

第一版，直覺地使用堆疊

「合乎規則的括號」意思是每個左括號的右邊都應該能找到對應的右括號，且一組括號內的子字串也應該符合規則。

所以可以想像，字串中可能有"()"、"[]"或"{}"，把這些字串中一組組的括號移除之後又應該產生其他組相鄰的括號，例如："([])"→"()"→""，這就可以使用堆疊的概念解題。

文字說明的邏輯如下：

依序由左到右確認每個字元，如果是左括號就放進堆疊，是右括號就確認是否與最後一個放入的左括號匹配，是則移除堆疊最上方的左括號，否則代表字串不合規則後續也不需確認了。

碰到右括號時也可能發生堆疊目前為空的情況，這也是不合規則的情況。
除此之外在檢查完每個字元後也要確認堆疊內的字元全數消化完畢，否則代表有落單的左括號不合乎規則。

使用功能：
stack.peak() 確認堆疊最上方字元的值
stack.pop() 移除堆疊最上方的字元

這版本的處理時間為2ms，與大多數解答接近，使用記憶體則是低於平均，在倒數30%(Beats 29.7%)。

第二版，根據堆疊功能與題目需求精簡程式

試著精簡程式邏輯，發現peak()功能是可以不使用的，因為每個存在堆疊的字元都只會比較一次，只要符合就移除字元，不符合就得到結果，因此可以改使用pop()取得字元比對的同時移除，再根據比對的結果決定是否判斷為不符合規則。

這改動只減少了6行，處理時間不變，但是記憶體使用效率排名大幅提升(Beats 78.37%)。

順帶一提合併判斷邏輯的寫法對效能沒有影響，不管是練習還是實務都建議以可讀性為準，個人傾向於不合併(下圖左側)

第三版，針對可讀性做修改

另外以個人開發的經驗其實比較不喜歡在判斷條件使用pop()這種會修改值的功能，希望盡量維持判斷就只做判斷的工作，寫成文字的差別大約是這樣：

if (pop()) {
    // do something
}

↓

item = pop();
if (item) {
    // do something
}

這是個人認為比較好讀的寫法，也是導致我在第一版多使用peak()這個純粹取值的功能的原因，有時實務也會碰到這種情況，因此寫完程式之後需要多看幾次確認有沒有更好的寫法。

第三版這樣修改之後與第二版的花費時間和記憶體幾乎一樣，雖然比第一版還多了幾行，但是是更理想的寫法。

第四版，將重複的邏輯抽出寫為共用函式呼叫

上述第二第三版修正的時候都需要對三種右括號一樣的邏輯做修改，解題的情況是三段程式都在同一個地方所以不至於漏掉，但是實務開發若分散在不同檔案就可能導致後續修改時少改到部分情境導致不同步，應避免這情況。

使用一個物件map記錄題目要求的三組括號字元，函式裡面以堆疊最上層的左括號字元之後取得map當中對應的右括號，再與傳入的值比對是否一致，回傳比對結果。

這個寫法的效能與第三版持平，但是如果要做後續擴展會更好修改，例如想要加入角括號('<'、'>')判斷的時候在switch加上新的case，並在map增加新的一組對應就行。

番外第一版，很符合直覺的爛方法

打從題目一開始的敘述，可能會有人有以下想法：「如果不使用堆疊，而是在迴圈之中呼叫replaceAll()功能把字串中的"()"、"[]"、"{}"移除，再把移除後的字串再次移除……持續到無法移除為止，再確認字串有沒有清空不就行了嗎？」

事實上是可行的答案(至少能得到結果)，但是這版程式的效率非常之差，超出200ms的時間花費是常規方法的百倍以上，記憶體使用也多了不少，並不是個好方法。

第一次用這樣說明中途每次改善的動機和內容的方式記錄，比想像中的麻煩，也在反覆嘗試提升效率的過程中注意到一件事：不用太過在意記憶體用量。

多數解答的記憶體用量差距都不大，甚至同樣的解答多次提交也可能有些微的記憶體差距導致排名差了10%以上，而背後純粹的用量可能只差了0.1MB。

所以除非是用了爛方法大幅落後他人的情況，否則練習的時候以程式精簡與可讀性為目標就好。