題目連結: https://leetcode.com/problems/longest-valid-parentheses/
Test cases:
Input: “" output: 0
Input: “(" output: 0
Input: “(()" output: 2
Input: “(())" output: 4
Input: “())()()" output: 4
Input: “()((()()" output: 4
解法參考:
https://zxi.mytechroad.com/blog/stack/leetcode-32-longest-valid-parentheses/
法ㄧ:
func longestValidParentheses(_ s: String) -> Int {
var result = 0
var start = 0
var stack: [Int] = []
for (index, c) in s.enumerated() {
if c == "(" {
stack.append(index)
} else {
if stack.isEmpty {
start = index + 1
} else {
stack.removeLast()
if let last = stack.last {
result = max(result, index - last)
} else {
result = max(result, index - start + 1)
}
}
}
}
return result
}
//自己練習的解法 (p.s. 最後一個case失敗,因為這個解法無法判斷由"("產生的間隔 )
func longestValidParentheses(_ s: String) -> Int {
var result: [Int] = []
var tmpResult = 0
var stack: [Character] = []
for c in s {
if c == "(" {
stack.append(c)
} else {
if let last = stack.last {
stack.removeLast()
tmpResult += 2
} else {
result.append(tmpResult)
tmpResult = 0
stack.removeAll()
}
}
}
if tmpResult != 0 {
result.append(tmpResult)
}
return result.max() ?? 0
}