Leetcode 1249.生成有效括号的最小删除数

Question

我需要帮助来理解以下问题的快速实现。我不理解的部分是for循环；循环的if部分将"0"的索引附加到"0"；("对于堆栈数组，我不确定else-if是如何从堆栈中弹出元素的。还有最后一个循环，它做什么？

*给定由"("，"("和小写英文字符组成的字符串s。您的任务是删除最小数量的括号("("或"("，位于任何位置(，以便生成的括号字符串有效，并返回任何有效字符串。形式上，括号字符串是有效的，当且仅当：

它是空字符串，只包含小写字符，或

它可以写成AB(A与B相连(，其中A和B是有效字符串，或者

它可以写成(A(，其中A是一个有效的字符串。*

func minRemoveToMakeValid(_ s: String) -> String {
var arraySrting = s.map({String($0)})
var stacks = [Int]()

for i in 0..<arraySrting.count{
if arraySrting[i] == "("{
stacks.append(i)
}
else if arraySrting[i] == ")" && stacks.popLast() == nil{
arraySrting[i] = ""
}
}
for stack in stacks {
arraySrting[stack] =  ""
}

return arraySrting.joined()

}

Answer 1

这些变量名拼写错误。这与可选字符相同，而不是使用空字符串的语言无关解决方案。

import Algorithms // `compacted()` is better than `compactMap { $0 }`
func minRemoveToMakeValid(_ s: String) -> String {
var characters: [Character?] = Array(s)
var unmatchedOpenParenthesisIndices: [Array.Index] = []
func removeUnpairedParenthesis(at index: Array.Index) {
characters[index] = nil
}
for (index, character) in characters.enumerated() {
switch character {
case "(":
unmatchedOpenParenthesisIndices.append(index)
case ")":
switch unmatchedOpenParenthesisIndices.popLast() {
case .some:
// This `)` was paired with a previous `(`.
break
case nil:
// This `)` was not.
removeUnpairedParenthesis(at: index)
}
default:
break
}
}
unmatchedOpenParenthesisIndices.forEach(removeUnpairedParenthesis)

return .init(characters.compacted())
}

不过，您可以更直接地构建characters，而unmatchedOpenParenthesisIndices可以是Set。

func minRemoveToMakeValid(_ s: String) -> String {
var characters: [Character?] = []
var unmatchedOpenParenthesisIndices: Set<Int> = []
for (index, character) in s.enumerated() {
switch character {
case "(":
unmatchedOpenParenthesisIndices.insert(index)
case ")":
switch unmatchedOpenParenthesisIndices.popFirst() {
case .some:
// This `)` was paired with a previous `(`.
break
case nil:
// This `)` was not.
characters.append(nil)
continue
}
default:
break
}
characters.append(character)
}
return .init(
characters.enumerated().compactMap {
unmatchedOpenParenthesisIndices.contains($0.offset)
? nil
: $0.element
}
)
}