• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift OC混编发布时间:2022-07-13
下一篇:
[置顶] Swift教程_CoreData实例(一)_构建storyboard发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap