【LeetCode】老虎证券面试-括号嵌套且满足优先级

LeetCode第20题：简单括号 力扣

题目描述：

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

例子：

示例 1：

输入：s = "()"
输出：true
示例 2：

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

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

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

解题思路：

1. 如果 c 是左括号，则入栈 pushpush；
2. 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 falsefalse。

解决边界问题：

1. 栈 stack 为空： 此时 stack.pop() 操作会报错；因此，我们采用一个取巧方法，给 stack 赋初值 ?? ，并在哈希表 dic 中建立 key: '?'，value:'?'key: ′? ′，value: ′? ′的对应关系予以配合。此时当 stack 为空且 c 为右括号时，可以正常提前返回 falsefalse；
2. 字符串 s 以左括号结尾： 此情况下可以正常遍历完整个 s，但 stack 中遗留未出栈的左括号；因此，最后需返回 len(stack) == 1，以判断是否是有效的括号组合。

解题代码：

class Solution:
    def isValid(self, s: str) -> bool:
        stack = ['?']
        kv = {'(':')', '[':']', '{':'}','?':'?'}
        for ch in s:
            if ch in kv.keys():
                stack.append(ch)
            elif stack and kv[stack.pop()] != ch: return False 
        res = False
        if len(stack) == 1:
            res = True
        return res

题目变种：

题目描述：

要求括号，满足：

1. 成对出现
2. 满足嵌套关系，{}中，可以有[], ()

解题思路：

在上述解题思路的基础上，在入栈的时候，做一个嵌套优先级的判断.

解题代码：

def isValid(s):
    stack = ['?']
    kv = {'(':')', '[':']', '{':'}','?':'?'}
    for ch in s:
        if ch in kv.keys():
            if ch == '{' and len(stack) >=2 and stack[-1] in {'(', '['}:
                return False
            if ch == '[' and len(stack) >=2 and stack[-1] in {'('}:
                return False
            stack.append(ch)
        elif kv[stack.pop()] != ch: return False
    res = False
    if len(stack) == 1:
        res = True
    return res