给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true

解法 1：

利用堆栈，遍历字符串的每个输入字符，如果是左括号，将其压入堆栈，如果是右括号，则从栈顶弹出左括号，如果栈顶左括号和输入右括号不匹配或堆栈为空，则说明不是有效字符串。

def is_valid(s):
    stack = []
    c_map = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c not in c_map:
            stack.append(c)
        elif not stack or c_map[c] != stack.pop():
            return False
    return not stack

执行用时 :16 ms
内存消耗 :11.9 MB

时间复杂度：压栈和出栈及 map 查找的时间复杂度都为 O(1)，每个左括号都需压栈和出栈， 每个右字符都需要 map 查找，所以时间复杂度为 O(n)。
空间复杂度：最糟糕的情况是将所有符号堆到栈上，所以空间复杂度为 O(n)。

解法 2：

遍历字符串将所有对称括号替换为空字符，判断最后结果是否为空，通过比较替换前后的字符串长度来判断是否需要继续替换。

def is_valid(s):
    lenth = 0
    while len(s) != lenth:
        lenth = len(s)
        s = s.replace('()', '').replace('{}', '').replace('[]', '')
    return len(s) == 0

执行用时 :52 ms
内存消耗 :12 MB

时间复杂度为：
空间复杂度为：O(1)

参考

https://leetcode-cn.com/problems/valid-parentheses/