leetcode-20-有效的括号

题目：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

思路：

1. 使用栈可以保证时间复杂度为O（n）
2. 将左括号加入栈
3. 检测右括号，如果栈顶元素能匹配，则将栈顶元素pop，不能匹配则直接返回false
4. 最后检测栈是否为空，为空即有效

code:

#ruby
def is_valid(s)
 hash = {')': '(', '}': '{', ']': '['}
    stack = []
    for i in 0...s.size
        if hash.values.include? s[i]
            stack << s[i]
        elsif (hash.keys.include? s[i].to_sym) && (stack[-1] == hash[s[i].to_sym])
            stack.pop
        else
            return false
        end
    end
    stack.empty?
end

#python3
class Solution:
    def isValid(self, s: str) -> bool:
        hash = {'{': '}',  '[': ']', '(': ')'}
        stack = []
        for c in s:
            if not stack or c in hash: stack.append(c)
            elif stack[-1] in hash and hash[stack[-1]] == c: stack.pop()
            else: return False  
        return not stack