[Swift]LeetCode1249.移除无效的括号|MinimumRemovetoMakeValidParentheses

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

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

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

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

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

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

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"
Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Example 4:

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5
s[i] is one of '(' , ')' and lowercase English letters.

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下任意一条要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：

输入：s = "a)b(c)d"
输出："ab(c)d"
示例 3：

输入：s = "))(("
输出：""
解释：空字符串也是有效的
示例 4：

输入：s = "(a(b(c)d)"
输出："a(b(c)d)"

提示：

1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小写字母

188ms

 1 class Solution {
 2     func minRemoveToMakeValid(_ s: String) -> String {
 3         var parentheses = Array<Int>()
 4         var deleteIndex = [Int]()
 5         var chars = [Character](s)
 6         for i in 0..<s.count {
 7             if chars[i] == "(" {
 8                 parentheses.append(i)
 9             } else if chars[i] == ")" {
10                 if parentheses.isEmpty {
11                     deleteIndex.append(i)
12                 } else {
13                     parentheses.removeLast()
14                 }
15             }
16         }
17         deleteIndex.append(contentsOf: parentheses)
18         let sortedIndex = deleteIndex.sorted { $0 > $1}
19         for index in sortedIndex {
20             chars.remove(at: index)
21         }
22         return String(chars)
23     }
24 }

192ms

 1 class Solution {
 2     func minRemoveToMakeValid(_ s: String) -> String {
 3         var leftParentheses = Array<Int>()
 4         var charsLeft = Array<Bool>(repeating: true, count: s.count)
 5         var chars = [Character](s)
 6         for i in 0..<s.count {
 7             if chars[i] == "(" {
 8                 leftParentheses.append(i)
 9             } else if chars[i] == ")" {
10                 if leftParentheses.isEmpty {
11                     charsLeft[i]  = false
12                 } else {
13                     leftParentheses.popLast()
14                 }
15             }
16         }
17         for i in 0..<leftParentheses.count {
18             charsLeft[leftParentheses[i]] = false
19         }
20 
21         var  ans = ""
22         for i in 0..<chars.count {
23             if charsLeft[i] {
24                 ans.append(chars[i])
25             }
26         }
27         return ans
28     }
29 }

240ms

 1 class Solution {
 2     func minRemoveToMakeValid(_ s: String) -> String {
 3         var opens = 0
 4         var result = [Character]()
 5         
 6         for char in s {
 7             if char != "(" && char != ")" {
 8                 result.append(char)
 9             } else if char == ")" {
10                 if opens > 0 {
11                     result.append(char)
12                     opens -= 1
13                 }
14             } else {
15                 opens += 1
16                 result.append(char)
17             }
18         }
19         
20         if opens == 0 {
21             return String(result)
22         }
23         
24         var realResult = [Character]()
25         
26         for char in result.reversed() {
27             if char == "(" && opens > 0 {
28                 opens -= 1
29                 continue
30             } else {
31                 realResult.append(char)
32             }
33         }
34         return String(realResult.reversed())
35     }
36 }

Runtime: 256 ms

Memory Usage: 25.7 MB

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