【LeetCode】括号的分数 Java 题解
题目描述
给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:
() 得 1 分。AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。(A) 得 2 * A 分,其中 A 是平衡括号字符串。
复制代码
思路分析
今天的算法题目字符串处理题目,具体的类型是括号处理题目,在括号处理题目中,我们最常使用栈这种数据结构来解决问题。
栈的性质是 LIFO(last in first out), 栈既有 Stack 这种数据结构,有时候也可以使用数组模拟实现。
具体到这个题目,本题要求的是括号的分数。为了求解方便,我们适当的做一些转换,把 ( 定义为 0。遇到 ) 出栈。从例子来看,"(())" 输出 2。 "()"输出 1。也可以转化为解括号深度的问题。具体实现代码如下:
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/a52f067be8fd4afc0b399d039】。文章转载请联系作者。
评论