valid-parentheses#20

发表于 更新于 分类于 本文字数： 172 阅读时长 ≈ 1 分钟

问题

有效的括号

String#isValid

定义扩展属性 String#isValid:

1
2
3
4
5
6
7
8
@Test
fun isValid() {
    assert("()".isValid)
    assert("()[]{}".isValid)
    assert(!"(]".isValid)
    assert(!"([)]".isValid)
    assert("{[]}".isValid)
}

单元测试

1
2
3
4
5
class Solution {
    fun isValid(s: String): Boolean {
        return s.isValid
    }
}

解法

辅助栈法

这个方法大二的时候数据结构课老师上课有讲过，解这道题非常好用的。

  • 初始化辅助站 helper
  • 依次处理表达式的每个括号
  • 如果遇到开括号，入栈
  • 如果遇到的是闭括号，出栈
  • 如果辅助栈不为空，则意味表达式无效

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 字符串是否有效
 */
private val String.isValid: Boolean
    get() {

        val helper = Stack<Char>()

        forEach { letter ->
            when {
                letter == '(' ->
                    helper.push(')')
                letter == '[' ->
                    helper.push(']')
                letter == '{' ->
                    helper.push('}')
                helper.isEmpty() || letter != helper.pop() ->
                    return false
            }
        }

        return helper.isEmpty()
    }