題目敘述
題目會給定一個字串s，裡面都是由() [] {}打散交錯而成。
問我們給定的輸入字串s 是不是合法括弧配對字串，也就是所有的右括弧都在左括弧後面，而且可以兩兩相消。測試範例
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
約束條件
Constraints:
1 <= s.length <= 104sconsists 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
