[LeetCode] 不用 Stack 改用 Recursion 來解 #20 Valid Parentheses
如果面試出這題我大概會說，阿不就用 stack，網路上隨便一找也如出一轍都用 stack。那如果不給你用 stack 呢? 何謂合法的一堆括號 LeetCode 解答一堆文字我真的覺得和上課或教科書沒兩樣，以前上課也是被灌輸這就是要用 stack，可是為什麼要用 stack? 之前的人怎麼知道的? 我們就用圖片來理解一下比較快: 如果我們把左邊和右邊的括號用一條線連起來，我們會發現他有一種把俄羅斯娃娃拆開放的感覺。 題目問是不是 valid，其實就是問拆開放的俄羅斯娃娃能不能組的回去? 說不定有人偷了一小塊，或是順序亂掉了就會變 invalid。 我也有點懶得做俄羅斯娃娃的圖片，所以我們直接來看一些 invalid 的範例: 最常見的 invalid 大概是第一個，我們把括號交錯放，如果不用 stack 就會誤判是 valid。 其他常見的 invalid 是找不到右邊的括號，或是左邊的括號不見了。 用 Stack 來做 為什麼大家這麼喜歡用 stack 來做這一題? 因為我們發現從左到右的順序剛好可以用 stack 的 push & pop 來代表: 任何破壞 stack 操作這樣 push & pop 的人都是 invalid。 我們按照這想法來寫一個很簡單的 C++ code 就會變成: class Solution { public: bool isValid(std::string s) { std::stack<char> leftParens; for (int i = 0; i < s.size(); i++) { const char c = s.at(i); if (isLeftParen(c)) { leftParens.push(c); } else { if (leftParens.empty()) return false; const char prevC = leftParens.top(); leftParens.pop(); if (!isPair(prevC, c)) return false; } } return leftP
