class Solution {
fun longestValidParentheses(s: String): Int {
val dp = IntArray(s.length)
var max = 0
for (i in 1 until s.length) {
dp[i] = when {
s[i] == ')' && s[i - 1] == '(' ->
(if (i >= 2) dp[i - 2] else 0) + 2
s[i] == ')' && i - 1 >= dp[i - 1] && s[i - 1 - dp[i - 1]] == '(' ->
dp[i - 1] + (if (i - 2 >= dp[i - 1]) dp[i - 2 - dp[i - 1]] else 0) + 2
else -> 0
}
max = maxOf(max, dp[i])
}
return max
}
}
相减:
class Solution {
fun longestValidParentheses(s: String): Int {
val stack = java.util.Stack<Int>()
stack.push(-1)
var max = 0
for (i in s.indices) {
when {
s[i] == '(' -> stack.push(i)
else -> {
stack.pop()
when {
stack.empty() -> stack.push(i)
else -> max = maxOf(max, i - stack.peek())
}
}
}
}
return max
}
}
扫描:
class Solution {
fun longestValidParentheses(s: String): Int {
return maxOf(s.scan(true), s.scan(false))
}
private fun String.scan(leftToRight: Boolean): Int {
var left = 0
var right = 0
var max = 0
var index = if (leftToRight) 0 else this.lastIndex
val step = if (leftToRight) 1 else -1
while (index < this.length && index > -1) {
when (this[index]) {
'(' -> left++
')' -> right++
}
when {
left == right -> max = maxOf(max, left)
(leftToRight && left < right) || (!leftToRight && left > right) -> {
left = 0
right = 0
}
}
index += step
}
return max * 2
}
}