有效字符串

难度简单

描述

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

有效字符串需满足:

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

注意空字符串可被认为是有效字符串。

题解

借助 这一数据结构的先进后出的特性可以解决此问题。主要是判断括号的闭合,分两类括号:

  • 开括号:'(', '[', '{'
  • 闭括号:')', ']', '}'

遍历字符串中的字符,如果是开括号就压入栈中,如果是闭括号,就弹出栈顶元素,弹出元素如果与闭括号不成对那就返回 False,否则继续遍历并判断。遍历完整个字符串,最后如果栈为空就说明为有效字符串,返回 True

此题描述中说空字符串也返回 True 其实也包含在上面的处理 的情况中,不必另行判断。

实现

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack = [String]()
        let table = ["(": ")","[": "]", "{": "}"]
        for c in s {
            let char = String(c)
            if table.keys.contains(char) {
                stack.append(char)
            } else {
                let topElement = stack.count == 0 ? "" : table[stack.popLast()!]
                if topElement != char {
                    return false
                }
            }
        }
        return stack.isEmpty
    }
}
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {'(': ')', '[': ']', '{': '}'}
        for c in s:
            if c in table:
                stack.append(c)
            else:
                top_element = '' if len(stack) == 0 else table[stack.pop()]
                if top_element != c:
                    return False
        return True if len(stack) == 0 else False