前往此题

解题思路

看到这种题首先应该想到的是通过哈希表来检查符号的对应关系。

哈希表可以在**O(1)**的时间复杂度下准确快速的找到对应字符, 为了方便确认字符串对应关系是否合理需要用到栈的出栈入栈功能

通过遍历整个字符与哈希表做对应检查, 如果存在对应关系则会入栈，如果找不到对应关系就提前返回false。因为栈一开始为空，所以需要临时加入？元素作为辅助作用

代码

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

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)