【LeetCode】0020. Valid Parentheses

| | |

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

An input string is valid if:

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

Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: True

Example 2:

1
2
Input: "()[]{}"
Output: True

Example 3:

1
2
Input:** "(]"
**Output:** false

Example 4:

1
2
Input:"([)]"
Output: False

Example 5:

1
2
Input: "{[]}"
Output: True


Related Topics:String、Stack

解題邏輯與實作

這題是在驗證括號是否成對，看到這種題目第一反應就是用 Stack：

  1. 依序遍歷輸入字串
    1. 若為左括號，則 push 進入 stack
    2. 若為右括號，則
      1. 若 Stack 為空，則回傳 False
      2. 若 Stack 不為空，則取出 Stack 頂端元素，判斷是否成對，若不成對則回傳 False，反之繼續向下執行。
  2. 直到字串遍歷完畢，且 Stack 為空，則回傳 True，反之回傳 False。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Stack(object):
   def __init__(self):
      self.stack=[]
   def isEmpty(self):
      return self.stack==[]
   def push(self,item):
      self.stack.append(item)
   def pop(self):
      if self.isEmpty():
         raise IndexError
      return self.stack.pop()
   def peek(self):
      return self.stack[-1]
   def size(self):
      return len(self.stack)
      
class Solution:
   def isValid(self, s: str) -> bool:
      match = {")":"(", "}":"{","]":"["}

      stack = Stack()
      legal = True
            
      for c in s:
         if c in match.values():
            stack.push(c)
         elif c in match.keys():
            if stack.isEmpty():
               legal=False
               break
            else:                              
               if match[c] !=   stack.pop():
                  legal = False
                  break
         else :
               legal=False
               break
                              
      if not stack.isEmpty():
         legal = False
            
      return legal



依照題目的輸入限制，進一步優化與精簡程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
   def isValid(self, s: str) -> bool:
      stack = []
      match = {")":"(", "}":"{","]":"["}

      for c in s:
         if c in match:
            if stack == [] or match[c] !=   stack.pop():
               return False
         else:
            stack.append(c)

      return stack == []

其他連結

  1. 【LeetCode】0000. 解題目錄