LeetCode算法学习日记（2020年8月）

2020.8.14

---

题目：有效的括号
解题思路：栈
示例：

输入： “( ) [ ] { }”
输出： true

输入： “( [ ) ]”
输出： false

代码：

    func isValid(_ s: String) -> Bool {       
    if s.isEmpty {
        return true
    }
    let dic:[Character:Int] = ["(":1,")":2,"[":3,"]":4,"{":5,"}":6]
    var arr = [s[s.startIndex]]
    var isSkip = false //是否清空
    for index in 1..<s.count {

        let currentS : Character = s[s.index(s.startIndex, offsetBy: index)]

        if isSkip {
            isSkip = false
            arr = [currentS]
            continue
        }

        let lastS : Character? = arr.last
        let currentNum = dic[currentS] // 当前符号代表的数
        let lastNum = dic[lastS!] // 栈顶符号代表的数
        if (lastNum! == 1 && currentNum! == 2) || (lastNum! == 3 && currentNum! == 4) || (lastNum! == 5 && currentNum! == 6){
            arr.removeLast()
        }else{
            arr.append(currentS)
        }
        isSkip = (arr.count == 0)

    }

    return arr.count > 0 ? false : true
}

算法理解：
当我们在遍历的时候，遇到左括号，就希望在后续中有右括号与之对应。根据先出现的左括号，延后对应，后出现的左括号，遇到右括号先对应的特点，栈的特点非常适合这道题的解题思路（先进后出）。
我们可以依次将一个符号压入栈顶，当有左括号遇到右括号时，两两相消，一直到最后如果栈内符号全部消除，则说明这组符号是有效的。

打赏