valid-parentheses#20

问题

有效的括号

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()
}