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

[Swift]LeetCode301.删除无效的括号|RemoveInvalidParentheses

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]

示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

示例 3:

输入: ")("
输出: [""]

20ms
 1 class Solution {
 2     func removeInvalidParentheses(_ s: String) -> [String] {
 3         var paths = [String]()
 4         dfs(&paths, Array(s), 0, 0, ("(", ")"))
 5         return paths
 6     }
 7     
 8     fileprivate func dfs(_ paths: inout [String], _ s: [Character], _ lastValid: Int, _ lastRight: Int, _ parens: (Character, Character)) {
 9         var count = 0, s = s
10         
11         for i in lastValid ..< s.count {
12             if s[i] == parens.0 {
13                 count += 1
14             }
15             
16             if s[i] == parens.1 {
17                 count -= 1
18             }
19             
20             if count < 0 {
21                 for j in lastRight ... i {
22                     guard s[j] == parens.1 else {
23                         continue
24                     }
25                     
26                     guard j == 0 || s[j] != s[j - 1] || j == lastRight else {
27                         continue
28                     }
29                     
30                     dfs(&paths, Array(s[0 ..< j] + s[j + 1 ..< s.count]), i, j, parens)
31                 }
32                 return
33             }
34         }
35         
36         if parens.0 == "(" {
37             dfs(&paths, s.reversed(), 0, 0, (")", "("))
38         } else {
39             paths.append(String(s.reversed()))
40         }
41     }
42 }

40ms

 1 class Solution {
 2     func removeInvalidParentheses(_ s: String) -> [String] {
 3         
 4         var res = [String]()
 5         var repeated  = Set<String>()
 6         removeRight(s, &res, &repeated)
 7         return res
 8     }
 9     
10     func removeRight(_ s : String, _ res : inout [String], _ repeated : inout Set<String>)  {
11         let sArr = Array(s)
12         var count = 0
13         for i in 0..<sArr.count {
14             let c = sArr[i]
15             if c == "(" {
16                 count += 1
17             }else if c == ")" {
18                 count -= 1
19             }
20             
21             if count < 0 {
22                 for j in 0...i where sArr[j] == ")" {
23                     let r = String(sArr[0..<j] + sArr[j+1..<sArr.count])
24                     if repeated.contains(r) {
25                         continue
26                     }
27                     repeated.insert(r)
28                     removeRight(r, &res, &repeated)
29                 }
30                 return
31             }
32         }
33         if count == 0 {
34             res.append(s)
35             return
36         }
37         
38         removeLeft(s, &res, &repeated)
39     }
40     
41     func removeLeft(_ s : String, _ res : inout [String], _ repeated : inout Set<String>)  {
42         let sArr = Array(s)
43         var count = 0
44         for i in stride(from: sArr.count-1, to: -1, by: -1) {
45             let c = sArr[i]
46             if c == ")" {
47                 count += 1
48             }else if c == "("{
49                 count -= 1
50             }
51             
52             if count < 0 {
53                 for j in stride(from: sArr.count-1, to: i-1, by: -1) where sArr[j] == "(" {
54                     let r = String(sArr[0..<j] + sArr[j+1..<sArr.count])
55                     if repeated.contains(r) {
56                         continue
57                     }
58                     repeated.insert(r)
59                     removeLeft(r, &res, &repeated)
60                 }
61                 return
62             }
63         }
64         res.append(s)
65     }
66 }

84ms

  1 class Solution {
  2   func isValid(_ str:String) -> Bool {
  3     
  4     var left = 0
  5     
  6     for char in str {
  7       
  8       if char == Character("(") {
  9         
 10         left += 1
 11       }
 12       
 13       if char == Character(")") {
 14         
 15         left -= 1
 16       }
 17       
 18       if left < 0 {
 19         
 20         return false
 21       }
 22     }
 23     
 24     return left == 0
 25   }
 26   
 27   func removeInvalidParentheses(_ s: String) -> [String] {
 28     
 29     var results:[String] = []
 30     
 31     if isValid(s) {
 32       
 33       return [s]
 34     }
 35     
 36     let mustRemove = findInvalid(s)
 37     
 38     removeAndCheck(s, start:0, left: mustRemove.left, right: mustRemove.right, &results)
 39     
 40     return results
 41   }
 42   
 43   func removeAndCheck(_ str:String, start:Int, left:Int, right:Int, _ results:inout [String]) {
 44     
 45     if left == 0 && right == 0 {
 46       
 47       if isValid(str) {
 48         
 49         results.append(str)
 50       }
 51       
 52       return
 53     }
 54     
 55     for i in start..<str.count {
 56       
 57       let index = str.index(str.startIndex, offsetBy: i)
 58       
 59       let next = str.index(after: index)
 60       
 61       if i != start {
 62         
 63         let prev = str.index(before: index)
 64         
 65         if str[index] == str[prev] {
 66           
 67           continue
 68         }
 69       }
 70       
 71       let char = str[index]
 72       
 73       if char == Character("(") && left > 0 {
 74         
 75         let substr = String(str[str.startIndex..<index] + str[next...])
 76         
 77         removeAndCheck(substr, start:i, left: left - 1, right: right , &results)
 78       }
 79       
 80       if char == Character(")") && right > 0 {
 81         
 82         let substr = String(str[str.startIndex..<index] + str[next...])
 83         
 84         removeAndCheck(substr, start:i, left: left, right: right - 1, &results)
 85       }
 86     }
 87   }
 88   
 89   func findInvalid(_ str:String) -> (left:Int, right:Int) {
 90     
 91     var cnt1 = 0, cnt2 = 0
 92     
 93     for char in str {
 94       
 95       if char == Character("(") {
 96         
 97         cnt1 += 1
 98       }
 99       
100       if cnt1 == 0 {
101       
102         if char == Character(")") {
103           
104           cnt2 += 1
105         }
106       }
107       else {
108         
109         if char == Character(")") {
110           
111           cnt1 -= 1
112         }
113       }
114     }
115     
116     return (cnt1, cnt2)
117   }
118 }

672ms

 1 class Solution {
 2     func removeInvalidParentheses(_ s: String) -> [String] {
 3         var result = [String]()
 4         var queue = [String]()
 5         var isFound = false
 6         var set = Set<String>()
 7         
 8         queue.append(s)
 9         
10         while !queue.isEmpty && !isFound {
11             let size = queue.count 
12             for _ in 0..<size {
13                 let s1 = queue.removeFirst()
14                 if isValid(s1) {
15                     result.append(String(s1))
16                     isFound = true
17                 } 
18                 
19                 if !isFound {
20                     let chars = Array(s1)
21                     for i in 0..<s1.count {
22                         
23                         if chars[i] != "(" && chars[i] != ")" {
24                             continue
25                         }
26                         
27                         if i > 0 && chars[i] == chars[i - 1] { 
28                             continue
29                         }
30                         
31                         var newChars = chars
32                         newChars.remove(at: i)
33                         let s2 = String(newChars)
34                         if !set.contains(s2) {
35                             queue.append(s2)
36                             set.insert(s2)
37                         }
38                     }
39                 }
40             }
41         }
42         
43         return result
44     }
45     
46     func isValid(_ s: String) -> Bool {
47         if s.isEmpty { return true }
48         var count = 0
49         for c in s {
50             if c == "(" {
51                 count += 1
52             } else if c == ")" {
53                 count -= 1
54                 if count < 0 {
55                     return false
56                 }
57             }
58         }
59         return count == 0
60     }
61 }

1196ms

 1 class Solution {
 2     let openers: Set<Character> = ["{", "[", "("]
 3     let closers: [Character: Character] = ["}":"{", ")": "(", "]": "["]
 4     
 5     func isCorrectlyParenthesized(_ s: String,
 6                                   visited: inout Set<String>,
 7                                   potentialSolutions: inout Set<String>,
 8                                   maxLength: inout Int) -> Bool {
 9         if visited.contains(s) {
10             return potentialSolutions.contains(s)
11         }
12         else {
13             visited.insert(s)
14         }
15         if s.count < maxLength {
16             return false
17         }
18         
19         guard let first = s.first else {
20             return true
21         }
22         var stack: [(char: Character, index: Int)] = (openers.contains(first) || closers[first] != nil) ? [(char: first, index: 0)] : []
23         var removedFromStack: [(char: Character, index: Int)] = []
24         
25         var str = s.dropFirst()
26         var i = 0
27         var failed = false
28         while !str.isEmpty {
29             let firstChar = str.removeFirst()
30             i += 1
31             
32             if openers.contains(firstChar) {
33                 stack.append((char: firstChar, index: i))
34                 continue
35             }
36             
37             guard closers[firstChar] != nil else {
38                 continue // it's OK to contain other characters.
39             }
40             
41             let stackLast = stack.isEmpty ? nil : stack.removeLast()
42             if let stackLast = stackLast { removedFromStack.append(stackLast) }
43             
44             if let stackLast = stackLast, closers[firstChar] != stackLast.char {
45                 failed = true
46                 break
47             }
48             else if stackLast == nil {
49                 failed = true
50                 break
51             }
52         }
53         
54         if !failed, stack.isEmpty, str.isEmpty {
55             let strlen = s.count
56             if maxLength <= strlen, !potentialSolutions.contains(s) {
57                 potentialSolutions.insert(s)
58                 maxLength = strlen
59             }
60             return true
61         }
62         if s.count >= 1 {
63             for substr in substringsWithParenthesisRemoved(from: s, earliestIndex: 0) {
64                 isCorrectlyParenthesized(substr, visited: &visited, potentialSolutions: &potentialSolutions, maxLength: &maxLength)
65             }
66         }
67         return false
68     }
69     
70     func substringsWithParenthesisRemoved(from str: String, earliestIndex: Int) -> [String] {
71         var out = [String]()
72         var i = str.index(str.startIndex, offsetBy: earliestIndex)
73         while i != str.endIndex {
74             let charI = str[i]
75             guard openers.contains(charI) || closers[charI] != nil else {
76                 i = str.index(after: i)
77                 continue
78             }
79             var outstr = str
80             outstr.remove(at: i)
81             out.append(outstr)
82             i = str.index(after: i)
83         }
84         return out
85     }
86     
87     func removeInvalidParentheses(_ s: String) -> [String] {
88         var potentialSolutions: Set<String> = []
89         var visited: Set<String> = []
90         var maxLen: Int = 0
91         isCorrectlyParenthesized(s, visited: &visited, potentialSolutions: &potentialSolutions, maxLength: &maxLen) ? potentialSolutions : []
92         let out = Array(potentialSolutions).filter { $0.count == maxLen }
93         return out.count > 0 ? out : [""]
94     }
95 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
swift之Mac中NSView视图里的截图【ScrollView中的内容截图】发布时间:2022-07-13
下一篇:
swift学习笔记之-协议发布时间: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