leetcode 20 有效的括号

思路:

一个符号数组,["{", "[", "(", "}", "]", ")"]一个栈。

  • 如果遇到左边的符号 0<= index < 3,则push栈
  • 如果遇到右边的符号 index > 2
    1. 首先先判断栈空不空。如果是空,则return false;
    2. 拿栈顶元素比较,如果匹配则继续进行。如果不匹配则return false.
    3. 当字符串都判断完毕,则判断栈是否为空。如果不空,则return false.
    4. return true

实现:

swift 没有栈,需要用数组实现一个:

struct Stack<T> {
    // 对数组进行初始化
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T) {
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        // 数组不为空时,返回并移除最后一个元素;空时,返回nil
        return array.popLast()
    }
    
    public var top: T? {
        //数组不为空时,返回最后一个元素;空时,返回nil
        return array.last
    }
}

// 判断符号是否成对匹配
func isValid(_ s: String) -> Bool {
    let charArray = Array(s)
    let symbelArray : [Character] = ["{", "[", "(", "}", "]", ")"]
    var stackStr = Stack<Character>()
    
    for item in charArray {
        if let index = symbelArray.index(of: item) {
            if index < 3 {
                // 如果是左括号,则进栈
                stackStr.push(item)
            }
            else {
                // 右括号
                if stackStr.isEmpty {
                    // 栈中没有元素,则不可能匹配
                    return false
                }
               
                // 如果栈中有元素,则拿栈顶元素匹配
                if let top = stackStr.top as? Character {
                    if symbelArray[index - 3] != top {
                        // 栈顶元素不匹配
                        return false
                    }
                    
                    // 栈顶元素匹配成功,则继续进行。
                    stackStr.pop()
                }
            }
        }
    }
    
    // 所有右边的括号都匹配了,如果栈还有元素,说明还有左括号没有匹配成功。
    return stackStr.isEmpty
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 问题描述 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 括号必须...
    Dy1an阅读 260评论 0 0
  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 4,208评论 0 13
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 135,010评论 19 139
  • 把月亮高高挂起 踩着父亲做的松木梯子 散发着酒香的梯子 听到大提琴会跳舞的梯子 直到时光回流 直到故乡的呼吸含苞待...
    孟小繁阅读 178评论 0 0
  • 岁月不堪 迷离了时光 街角的纯美 碎了一地的忧伤 那时不再 思念转愁肠 离去 湮了情 灭了伤
    紫灬楓阅读 120评论 0 0