[LeetCode] 020. 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:

Input: "()"
Output: True



Example 2:

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



Example 3:

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



Example 4:

Input:"([)]"
Output: False



Example 5:

Input: "{[]}"
Output: True


解題邏輯與實作

這題是在驗證括號是否成對,看到這種題目直覺就是用Stack:

  1. 依序遍歷輸入字串
    1. 若為左括號,則push進入stack
    2. 若為右括號,則
      1. 若Stack為空,則回傳False
      2. 若Stack不為空,則取出stack頂端元素,判斷是否成對,若不成對則回傳False,反之繼續向下執行。
  2. 直到字串遍歷完畢,且Stack為空,則回傳True,反之回傳False



程式碼

from pythonds.basic.stack import Stack 
class Solution:
    def isValid(self, s):
        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



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET