[Swift]LeetCode32. 最长有效括号 | Longest Valid Parentheses

时间：2022-02-26 06:20:35

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 }

 

标签：

相关文章