美文网首页
LeetCode_Python(20)_有效的括号

LeetCode_Python(20)_有效的括号

作者: 惑也 | 来源:发表于2019-01-25 21:42 被阅读24次

    需求

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

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

    示例 1
    输入: "()"
    输出: true

    示例 2
    输入: "()[]{}"
    输出: true

    示例 3
    输入: "(]"
    输出: false

    示例 4
    输入: "([)]"
    输出: false

    示例 5
    输入: "{[]}"
    输出: true

    解决方案


    方法一

    1. 根据需求,左右必须是同类型的括号,且各类符号之间可以互相包含,但不能交叉,一旦出现交叉情况则说明是无效字符;

    2. 循环判断字符串中是否存在()[]{},如果存在则替换为空字符,直到将所有的括号剔除,如果最后字符串为空则说明是有效字符,否则是无效字符

    3. 参考代码

    def is_valid(s):
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        return s == ''
    
    s = '{([()})]'
    print(is_valid(s))
    False
    

    方法二

    1. 构建以右括号为key,左括号为value的字典;

    2. 遍历字符串
      为左括号时,直接添加到中间结果;
      为右括号时,通过字典获取对应的左括号,与中间结果的最后一个元素对比。1)如果不相等则说明是无效字符串,结束遍历,直接返回False;2)如果相等则删除中间结果的最后一个元素,继续遍历直到结束;
      遍历结束后,如果中间结果长度为1(默认的空字符),说明添加的左括号都存在有效的右括号而被删除,是有效字符,否则是无效的。

    3. 参考代码

    def is_valid(s):
        d = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        item = [' ']
        
        for i in s:
            j = d.get(i, '')
            if item[-1] == j:
                item.pop()
            elif j:
                return False
            else:
                item.append(i)
        return len(item) == 1
    
    s = '{([()})]'
    print(is_valid(s))
    False
    

    方法三

    1. 该方法与方法二的思路一样,构建右括号对应左括号的字典,遍历字符串进行判断,该方法更简洁优雅,好理解;

    2. 遍历字符串
      为左括号时,添加到中间结果,结束本次循环,开始下次循环;
      为右括号时:1)如果中间结果为空时,说明是无效字符串,结束循环返回False;2)中间结果不为空,对中间结果进行pop()操作(默认删除最后一个元素),返回删除的元素,与右括号对比,如果不相等则说明是无效字符串,结束循环返回False;如果相等继续遍历直到结束;
      遍历结束后,如果中间结果为空,说明添加的左括号都存在有效的右括号而被删除,是有效字符,否则是无效的。

    3. 参考代码

    def is_valid(s):
        d = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        item = []
    
        for i in s:
            if i not in d:
                item.append(i)
                continue
            if not item or item.pop() != d[i]:
                return False
        return len(item) == 0
    
    s = '{([()})]'
    print(is_valid(s))
    False
    

    相关文章

      网友评论

          本文标题:LeetCode_Python(20)_有效的括号

          本文链接:https://www.haomeiwen.com/subject/kgovjqtx.html