Stack堆疊應用題 合法括號配對字串 Leetcode #20_Valid Parentheses

這題的題目在這裡:

題目敘述

題目會給定一個字串s，裡面都是由() [] {}打散交錯而成。

問我們給定的輸入字串s 是不是合法括弧配對字串，也就是所有的右括弧都在左括弧後面，而且可以兩兩相消。

測試範例

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

約束條件

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

演算法

使用字典建立左右括號的配對關係應設，和stack檢查配對括號的技巧。

底層資料結構使用stack，藉由FILO, First-in last-out的特性來協助判斷。

每遇到一個左括號就推入stack，

每遇到一個右括號，就檢查頂部是不是對應的左括號，假如是，就一起pop出來。假如不是，直接return False 代表不是合法配對字串。

最後都配對完，stack應該要為空(empty stack)。

程式碼

class Solution:
　def isValid(self, s: str) -> bool:
　　
　　stack = []
　　
　　# mapping relationship
　　# key: right bracket
　　# value: corresponding left bracket
　　pair = { 
　　　　　')':   '(',
　　　　　']':   '[',
　　　　　'}':   '{'
　　　　}
　　
　　
　　left_bracket = set( pair.values() )
　　top_index = -1
　　
　　for char in s:
　　　
　　　if char in left_bracket:
　　　　# push left bracket into stack
　　　　stack.append(char)　　
　　　
　　　elif not stack or (stack[top_index] != pair[char]):
　　　　# Cannot match if stack is empty, or corresponding right bracket does not exist
　　　　return False
　　　
　　　else:
　　　　# Match if we have corresponding right bracket on top layer of stack
　　　　stack.pop()
　　　　
　　return len(stack) == 0

複雜度分析

時間複雜度: O( n )
從頭到尾，每個字元檢查過一遍。

空間複雜度: O( n )
需要一個stack，stack耗用空間最多和字串長度一樣長。

關鍵知識點

在於理解並且活用stack 先進後出FILO的特質，來實作括號配對。
並且利用dictionary字典來儲存左右括號的配對映射關係。

Reference:

[1] Python/Go/C++ O(n) by stack [w/ Comment] 有 中文詳解 解題影片 - Valid Parentheses - LeetCode