Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

20. Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

1
2
Input: s = "()"
Output: true

Example 2:

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

Example 3:

1
2
Input: s = "(]"
Output: false

Example 4:

1
2
Input: s = "([)]"
Output: false

Example 5:

1
2
Input: s = "{[]}"
Output: true

定義符號對,遇到符號押入,配對成功移出,檢查陣列是否空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Time: O(n), Space: O(n)

class Solution(object):
def isValid(self, s):
mapping = {
"(": ")",
"[": "]",
"{": "}"}
left = set(["(", "[", "{"])
stack = []
for i in s:
if i in left: # match left
stack.append(i) # append left
elif stack and i == mapping[stack[-1]]: # stack not null and is right
stack.pop() # pop left
else:
return False
return stack == [] # stack empty, all matched

如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Welcome to my other publishing channels