给定一个只包括 '(',')','{','}','[',']' 的字符串 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% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/349