問題

https://leetcode.com/problems/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:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

我的答案

使用Stack.

當遇到[ { (時，呼叫 stack.push()
當遇到 ] } )時，呼叫 stack.pop()
最後只要確定Stack是空的就可以了

class Solution:
    def isValid(self, s: str) -> bool:

        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in mapping :
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

Go

注意 Go 語言中，字串中每個字元的資料格式是byte．

func isValid(s string) bool {
    stack := []byte{}
    mapping := map[byte]byte{
        ')':'(' , 
        ']':'[' , 
        '}':'{',
    }
    for i := 0; i < len(s); i++ {
        val, exist := mapping[s[i]]
        if exist {
            if len(stack) > 0 {
                top_element := stack[len(stack)-1]
            } else {
                return false
            }
            if val != top_element {
                return false
            }
            // Pop the top element
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    if len(stack) > 0 {
        return false
    }
    return true
}