合縱連橫: 從 括弧配對 理解 配對模型與Stack應用
這篇文章，會帶著大家複習以前學過的配對模型與Stack框架，
並且以括弧配對的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
首先，Stack本身具有Last-In First-Out 後進先出的特質。
再根據題目所需要的資訊利用Stack去儲存索引、字串，
進行括弧配對相關的檢查或者計算。
常見的配對模型的Stack框架
stack, TOP = [], -1
for symbol in input:
if stack[TOP] is matched( ... ):
# 做某些配對需要的計算或檢查
# 把把配對成功的()pop出來
if allowed( ... )
# 如果符合題意，推入新的symbol進入stack頂端
return 最終結果(True/False，或者最後配對成功的字串)
配對模型常用的用途
1.檢查輸入字串是否為合法配對。
2.計算合法配對的長度。
3.生成合法配對的字串。
接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種 前綴和 框架，之後的解說會反覆出現)
有些題目剛好以前有錄過教學影片，提供給讀者參考。
Valid Parentheses 檢查是否為合法配對字串
這算是一個很常見的入門基本題。
想法也很直覺，就是遇到左(就推入，遇到)括號就pop出對應的左(
如果最後檢查完，stack剛好是空的，代表輸入字串是一個合法配對。
依照配對模型+stack框架拓展的解題程式碼
class Solution:
def isValid(self, s: str) -> bool:
stack = []
## dictionary
# key: right bracket
# value: corresponding left bracket
pair = {
')':'(',
']':'[',
'}':'{',
}
for char in s:
if char in pair:
# check when we meet right parenthesis
if (not stack) or ( stack and (stack[-1] != pair[char]) ):
# parenthesis mismatch
return False
else:
# parenthesis match
stack.pop()
else:
# push left parenthesis into stack
stack.append( char )
# Accept if all parenthesis pair are matched.
return not stack
Removing Stars From a String 從字串中移除*號
根據題意，
可以知道*其實是在模擬鍵盤上的backsapce鍵，相當於往左邊吃掉一個字元。
轉換到配對模型，就相當於，把*星號和前面最接近的字元做配對，並且pop出來，
最後留在stack內的字元，串接轉換成字串，就是最終移除*號的結果。
依照配對模型+stack框架拓展的解題程式碼，相當簡潔!
class Solution:
def removeStars(self, s: str) -> str:
stk = []
for char in s:
if char != '*':
stk.append( char )
else:
stk.pop()
return "".join(stk)
Longest Valid Parentheses 合法配對的最長長度
前面的題目，已經會檢查了，那如果要計算合法配對的最長長度也是類似的。
遇到(括號或者stack已經為空時，推入當下的索引。
遇到)括號就pop (括號出來，並且計算、更新合法配對的最長長度。
這邊有一個實作的細節需要留意，為了處理stack為空的狀態，
我們會事先在stack推入-1來代表stack為空，已經到達最底部，沒有東西了。
依照配對模型+stack框架拓展的解題程式碼
class Solution:
def longestValidParentheses(self, s: str) -> int:
# stack, used to record index of parenthesis
# initialized to -1 as dummy head for valid parentheses length computation
stack = [-1]
max_length = 0
# linear scan each index and character in input string s
for cur_idx, char in enumerate(s):
if char == '(':
# push when current char is (
stack.append( cur_idx )
else:
# pop when current char is )
stack.pop()
if not stack:
# stack is empty, push current index into stack
stack.append( cur_idx )
else:
# stack is non-empty, update maximal valid parentheses length
max_length = max(max_length, cur_idx - stack[-1])
return max_length
Generate Parentheses 生成指定長度的合法配對
剛剛已經會檢查、計算合法配對長度了。
那如果是要求我們從無到有生成指定長度的合法配對呢?
其實也是類似的，只是過程反過來而已。
一開始從空字串出發，每回合依序在尾巴加上( 或者 )
如果到某一回合，發現( 和 ) 的數目相等，而且等於n，
代表已經製造出一個合法括號配對字串，加入到最終結果裡面。
依照配對模型+stack框架拓展的解題程式碼
class Solution:
def generateParenthesis(self, n):
# storage of final result
result = []
# content, left brace count, right brace count
stack = [("", 0, 0)]
while stack:
x, l, r = stack.pop()
if l - r < 0 or l > n or r > n:
# Skip invalid cases
continue
if l == n and r == n:
# Valid pair, add into final result
result.append(x)
# add one more left brace
stack.append((x+"(", l+1, r))
# add one more right brace
stack.append((x+")", l, r+1))
return result
結語
好，今天一口氣介紹了最精華的部分，
通用的配對模型+Stack框架，還有相關的合法配對的檢查、長度計算、與字串生成
應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
