20. Valid Parentheses 有效的括號

有效字串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。

注意空字串可被認爲是有效字串。

範例 1:

輸入: "()"
輸出: true

範例 2:

輸入: "()[]{}"
輸出: true

範例 3:

輸入: "(]"
輸出: false

範例 4:

輸入: "([)]"
輸出: false

範例 5:

輸入: "{[]}"
輸出: true

棧

括號匹配嘛，最近點的棧問題。

Code

	def isValid(self, s: str) -> bool:
		if len(s) % 2 != 0:
			return False

		stack = []
		for c in list(s):
			if c in ['(', '[', '{']:
				stack.append(c)
			elif c == ')' and (len(stack) == 0 or stack.pop() != '('):
				return False
			elif c == ']' and (len(stack) == 0 or stack.pop() != '['):
				return False
			elif c == '}' and (len(stack) == 0 or stack.pop() != '{'):
				return False
		return len(stack) == 0

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 是字串 $s$ 的長度。

• 空間複雜度：$O(n+|\Sigma |)$，其中 $\Sigma$ 表示字元集，本題中字串只包含 $6$ 種括號，$|\Sigma |=6$。棧中的字元數量爲 $O(n)$，而雜湊對映使用的空間爲 $O(|\Sigma |)$，相加即可得到總空間複雜度。