[Swift]LeetCode32.最长有效括号|LongestValidParentheses

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9898451.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

【使用堆栈】算法

我们可以在扫描给定字符串时使用堆栈来检查目前为止扫描的字符串是否有效，以及最长有效字符串的长度，而不是查找每个可能的字符串并检查其有效性。为了做到这一点，我们从推动开始-1- 1到堆栈。

每一个 \文本{'（'}'（'遇到，我们将其索引推入堆栈。

每一个 \文本{'）'}'）'遇到，我们弹出最顶层的元素并从堆栈的顶部元素中减去当前元素的索引，这给出了当前遇到的有效括号字符串的长度。如果在弹出元素时，堆栈变空，我们将当前元素的索引推送到堆栈。通过这种方式，我们继续计算有效子串的长度，并在结尾返回最长有效字符串的长度。

2828ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         var maxans:Int = 0
 4         var stack:Stack<Int> = Stack<Int>()
 5         stack.push(-1)
 6         for i in 0..<s.count
 7         {
 8             if s.charAt(i) == "("
 9             {
10                 stack.push(i)
11             }
12             else
13             {
14                 stack.pop()
15                 if stack.isEmpty()
16                 {
17                     stack.push(i)
18                 }
19                 else
20                 {
21                     maxans = max(maxans, i - stack.getLast()!)
22                 }
23             }
24         }
25         return maxans
26     }
27 }
28 extension String {
29     //获取指定索引位置的字符，返回为字符串形式
30     func charAt(_ num:Int) -> String
31     {
32         let index = self.index(self.startIndex,offsetBy: num)
33         return String(self[index])
34     }
35 }
36 
37 public struct Stack<T> {
38     
39     // 泛型数组：用于存储数据元素
40     fileprivate var stack: [T] 
41 
42 
43     /// 构造函数：创建一个空的堆栈
44     public init() {
45         stack = [T]()
46     }
47     
48     //通过既定数组构造堆栈
49     init(_ arr:[T]){
50         stack = arr
51     }
52     
53     // 如果定义了默认值，则可以在调用函数时省略该参数
54     init(_ elements: T...) {
55         stack = elements
56     }
57     
58     // 检查堆栈是否为空
59     // - returns: 如果堆栈为空，则返回true，否则返回false
60     public func isEmpty() -> Bool {
61         return stack.isEmpty
62     }
63     
64     // 入堆栈操作：将元素添加到堆栈的末尾
65     public mutating func push(_ element: T) {
66         stack.append(element)
67     }
68     
69     // 出堆栈操作：删除并返回堆栈中的第一个元素
70     public mutating func pop() -> T? {
71         return stack.removeLast()
72     }
73  
74     // 返回堆栈中的第一个元素(不删除)
75     public func getLast() -> T? {
76         return stack.last!
77     }
78 }

16ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         let s = Array(s.characters)
 4         let len = s.count
 5         var max = Array(repeating: 0, count: len)
 6         var i = len-2
 7         var res = 0
 8         while i >= 0 {
 9             // find max[i]
10             if s[i] == ")" {
11                 i -= 1
12                 continue
13             }
14             
15             // s[i] = '('
16             if s[i+1] == ")" {
17                 max[i] = 2 + (i < len-2 ? max[i+2] : 0)
18             } else {
19                 let j = i + 1 + max[i+1];
20                 if j < len && s[j] == ")" {
21                     max[i] = 2 + max[i+1] + (j < len-1 ? max[j+1] : 0)
22                 }
23             }
24             
25             if max[i] > res { res = max[i] }
26             
27             i -= 1
28         }
29         
30         return res
31     }
32 }

20ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         
 4         guard s.count>0 else { return 0}
 5         
 6         var dp = Array(repeating:0,count:s.count)
 7         var sarr = Array(s.characters)
 8         var maxLen = 0
 9     
10         //print(sarr)
11         for i in 1..<sarr.count {
12             if(sarr[i]==")") {
13                 if(sarr[i-1]=="(") {  //()
14                 dp[i] = (i>=2 ? dp[i-2]: 0) + 2
15                 //print("i:",i,"dp[i]:",dp[i])
16                 
17                 }
18                 else {  // ))
19                     var prevIdx = i-dp[i-1]-1
20                     //print("prevIdx:",prevIdx)
21                     //print(dp)
22                 
23                     if(prevIdx>=0 && sarr[prevIdx] == "(") {  //We found another enclosing parantheses
24                         dp[i] = dp[i-1] + 2 + (prevIdx-1>=0 ? dp[prevIdx-1] : 0)
25                     }
26                 }
27             }
28         
29             if(dp[i]>=0) {
30                 maxLen = max(dp[i],maxLen)
31             }
32         }
33     
34         return maxLen
35     }
36 }

24ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         if s.count == 0{
 4             return 0
 5         }
 6         
 7         var stack = [Int]()
 8         stack.append(-1)
 9         var arr = Array(s)
10         var res = 0
11         for i in 0..<arr.count{
12             if arr[i] == ")"{
13                 if stack.count > 1 && arr[stack.last!] == "("{
14                     stack.removeLast()
15                     res = max(res, i - stack.last!)
16                 }else{
17                     stack.append(i)
18                 }
19             }else{
20                 stack.append(i)
21             }
22         }
23         return res
24     }
25 }

40ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         typealias Element = (index: Int, isOpening: Bool)
 4         var stack = [Element]()
 5         var maxCount = 0
 6         for (i, char) in s.enumerated() {
 7             if char == "(" {
 8                 stack.append((index: i, isOpening: true))
 9             } else {
10                 if !stack.isEmpty && stack.last!.isOpening {
11                     stack.removeLast()
12                     let lastIndex = stack.last?.index ?? -1
13                     let currentCount = i - lastIndex
14                     maxCount = max(maxCount, currentCount)
15                 } else {
16                     stack.append((index: i, isOpening: false))
17                 }
18             }
19         }
20         return maxCount
21     }
22 }

48ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         var stack: [Int] = [-1]
 4         var array = Array(s)
 5         var res = 0
 6         for i in 0..<array.count {
 7             if array[i] == "(" {
 8                 stack.append(i)
 9             } else if array[i] == ")" {
10                 stack.removeLast()
11                 if !stack.isEmpty {
12                     if (i - stack.last!) > res {
13                         res = (i - stack.last!)
14                     }
15                 } else {
16                     stack.append(i)
17                 }   
18             }
19         }
20         return res
21     }
22 }

56ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         var stack = Array<String>()
 4         var indexStack = Array<Int>()
 5         var i = 0
 6         for c in s{
 7             if c == ")"{
 8                 if stack.count == 0 || stack.last != "("{
 9                     stack.append(")")
10                     indexStack.append(i)
11                 }else{
12                     stack.removeLast()
13                     indexStack.removeLast()
14                 }
15             }else{
16                 stack.append("(")
17                 indexStack.append(i)
18             }
19             i += 1
20         }
21         var maxLength = 0
22         var lastIndex = -1
23         indexStack.append(s.count)
24         for i in indexStack{
25             let length = i - lastIndex - 1
26             maxLength = maxLength < length ? length : maxLength
27             lastIndex = i
28         }
29         return maxLength
30     }
31 }

72ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         var stack = [-1]
 4         var left = 0 // 左括号剩余
 5         
 6         for char in s {
 7             if char == "(" {
 8                 stack.append(0)
 9                 left += 1
10             } else {
11                 if left > 0 {
12                     left -= 1
13                     let top = stack.last!
14                     stack.removeLast()
15                     let second = stack.last!
16                     if top == 0 { // 左边即是括号
17                         if second == -1 || second == 0 { // 边界 或 左括号
18                             stack.append(2)
19                         } else { // 数字
20                             stack.removeLast()
21                             stack.append(second + 2)
22                         }
23                     } else { // 数字
24                         // 因为左括号数量大于0  因此second只能为左括号
25                         stack.removeLast()
26                         let third = stack.last!
27                         if third == -1 || third == 0 {
28                             stack.append(top + 2)
29                         } else { // 加上前一个数字
30                             stack.removeLast()
31                             stack.append(third + top + 2)
32                         }
33                     }
34                 } else {
35                     stack.append(-1)
36                 }
37             }
38         }
39         
40         var result = 0
41         for answer in stack {
42             result = max(answer, result)
43         }
44         return result
45     }
46 }

88ms

 1 class Solution {
 2     func longestValidParentheses(_ s: String) -> Int {
 3         var stack: [Character] = []     // 模拟一个栈
 4         var symbols: [Int] = []         // 将括号打标记，遇到 ( 标记为-1，遇到 ) 判断是否与栈顶配对，如果配对打标记1，否则打标记-1
 5         
 6         for c in s {
 7             if c == "(" {
 8                 stack.append(c)
 9                 symbols.append(-1)
10             } else if c == ")" {
11                 if stack.count > 0 && stack.last == "(" {
12                     let _ = stack.removeLast()
13                     symbols.append(1)
14                 } else {
15                     stack.append(c)
16                     symbols.append(-1)
17                 }
18             }
19         }
20         
21         var count: Int = 0          // 累加标记的数值
22         var tmpLength: Int = 0      // 临时保存的最长序列的长度
23         var maxLength: Int = 0      // 有效的最长序列的长度
24         
25         /*
26          )()())  ->  -1 -1 1 -1 1 -1
27          从右边遍历累加，成对的有效序列的和肯定是0，遇到-1，说明连续的序列断了，就重新累计
28          */
29         for num in symbols.reversed() {
30             count += num
31             
32             if count == -1 {
33                 count = 0
34                 maxLength = max(maxLength, tmpLength)
35                 tmpLength = 0
36             } else {
37                 tmpLength += 1
38             }
39         }
40         
41         if count == 0 {
42             maxLength = max(maxLength, tmpLength)
43         }
44         
45         return maxLength
46     }
47 }