LeetCode刷题 NO.20 有效的括号 (简单)

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

有效字符串需满足：

1）左括号必须用相同类型的右括号闭合。

2）左括号必须以正确的顺序闭合。

示例

输入：s = "()[]{}"  输出：true

输入：s = "{[]}"  输出：true

解析

1）这道题在之前介绍栈结构时做过，数据结构之栈与括号匹配问题

2）构造栈结构太复杂，可以用列表模拟

3）本题的关键就是找对应关系，先把括号压入栈中

4）右括号需要到栈中找左括号的对应，找到了则左括号出栈，没有则继续入栈

5）最后判断栈是否为空，为空则表示全部匹配上了

代码示例

def isValid(s: str) -> bool:
    if len(s) % 2 != 0:
        return False
    dct = {')':'(', '}':'{', ']':'['}
    lst = []
    for i in s:
        if lst == []:
            lst.append(i)
            continue
        if i in dct and dct[i] == lst[-1]:
            lst.pop()
        else:
            lst.append(i)
    return len(lst) == 0

s = "(){[]"
print(isValid(s))

执行用时：32 ms, 在所有 Python3 提交中击败了 92.32% 的用户.