合縱連橫: 從 括弧配對 理解 配對模型與Stack應用

Arteum.ro null on Unsplash

這篇文章，會帶著大家複習以前學過的配對模型與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框架，還有相關的合法配對的檢查、長度計算、與字串生成
應用題與演算法建造，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~