[Swift]LeetCode921.使括号有效的最少添加|MinimumAddtoMakeParenthesesValid ...

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

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

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

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

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

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

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

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

It is the empty string, 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.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: 1

Example 2:

Input: 3

Example 3:

Input: 0

Example 4:

Input: 4

Note:

S.length <= 1000
S only consists of '(' and ')' characters.

给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入："())"
输出：1

示例 2：

输入："((("
输出：3

示例 3：

输入："()"
输出：0

示例 4：

输入："()))(("
输出：4

提示：

S.length <= 1000
S 只包含 '(' 和 ')' 字符。

12ms：直觉与算法

跟踪字符串的平衡：'(''s的数量减去's的数量')'。如果字符串的平衡为0，则该字符串有效，并且每个前缀都具有非负平衡。

上述想法在匹配括号问题时很常见，但如果您之前没有看过，可能很难找到。

现在，考虑每个前缀的平衡S。如果它是负数（比如-1），我们必须添加一个'（'括号。另外，如果平衡S是正数（比方说+B），我们必须B在末尾添加'）'括号。

 1 class Solution {
 2     func minAddToMakeValid(_ S: String) -> Int {
 3         var ans:Int = 0 , bal:Int = 0
 4         for index in S.indices
 5         {
 6             bal += S[index] == "(" ? 1 : -1
 7             if bal == -1
 8             {
 9                 ans += 1
10                 bal += 1
11             }
12         }
13         return ans + bal
14     }
15 }

16ms

 1 class Solution {
 2     func minAddToMakeValid(_ S: String) -> Int {
 3         var incompleteSymbols: [Character] = []
 4         
 5         S.forEach { character in
 6             if let lastIncomplete = incompleteSymbols.last {
 7                 if lastIncomplete == "(" && character == ")" {
 8                     incompleteSymbols.removeLast()
 9                 }
10                 else {
11                     incompleteSymbols.append(character)
12                 }
13             }
14             else {
15                 incompleteSymbols.append(character)
16             }
17         }
18         
19         return incompleteSymbols.count
20     }
21 }

20ms

 1 class Solution {
 2     func minAddToMakeValid(_ S: String) -> Int {
 3         if(S == ""){
 4             return 0
 5         }
 6         
 7         var arrS = Array(S).map{"\($0)"}
 8         var open = 0
 9         var unclosed = 0
10         for c in arrS {
11             if(c == "(") { 
12                 open += 1 
13             }
14             if(c == ")") { 
15                 if( open > 0){
16                     open -= 1
17                 } else {
18                     unclosed += 1
19               }
20             }
21         }
22         var total = (open + unclosed)
23         return total 
24     }
25 }

20ms

 1 class Solution {
 2     func minAddToMakeValid(_ S: String) -> Int {
 3         var arr = [Character]()
 4         S.forEach { (c) in
 5              if arr.count>0 &&  arr[arr.count-1] == "(" && c == ")" {
 6                 arr.removeLast()
 7             } else { arr.append(c) }
 8         }
 9         return arr.count
10     }
11 }

64ms

 1 class Solution {
 2     func minAddToMakeValid(_ S: String) -> Int {
 3         var stack = [String]()
 4         
 5         for i in 0..<S.count {
 6             if S[i] == "(" {
 7                 stack.append(S[i])
 8             } else if S[i] == ")" && stack.last == "(" {
 9                 stack.removeLast()
10             } else {
11                 stack.append(S[i])
12             }
13         }
14         
15         return stack.count
16     }
17 }
18 
19 extension String {
20     subscript(i:Int) -> String {
21         let charIndex = self.index(self.startIndex, offsetBy: i)
22         return String(self[charIndex])
23     }
24 }