共计 1296 个字符，预计需要花费 4 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 921. 使括号无效的起码增加 ，难度为 中等。
Tag :「模仿」
只有满足上面几点之一，括号字符串才是无效的：
- 它是一个空字符串，或者
- 它能够被写成
AB（A与B连贯）, 其中A和B都是无效字符串，或者 - 它能够被写作 (
A)，其中A是无效字符串。
给定一个括号字符串 s，挪动 N 次，你就能够在字符串的任何地位插入一个括号。
- 例如，如果
s = "()))"，你能够插入一个开始括号为"(()))"或完结括号为"())))"。
返回 为使后果字符串 s 无效而必须增加的起码括号数。
示例 1：
输出：s = "())"
输入：1示例 2：
输出：s = "((("
输入：3提醒：
- $1 <= s.length <= 1000$
s只蕴含'('和')'字符
模仿
一个介绍过很屡次的做法 : 将「无效括号问题」转化为「分值有效性」的数学断定。
应用 score 代指处理过程中的得分，将 ( 记为 +1，将 ) 记为 -1。
一个无效的括号该当在整个过程中不呈现正数，因而一旦 score 呈现正数，咱们须要马上减少 ( 来确保合法性；当整个 s 解决完后，还须要增加 socre 等同的 ) 来确保合法性。
Java 代码：
class Solution {public int minAddToMakeValid(String s) {
int score = 0, ans = 0;
for (char c : s.toCharArray()) {
score += c == '(' ? 1 : -1;
if (score < 0) {score = 0; ans++;}
}
return ans + score;
}
}TypeScript 代码：
function minAddToMakeValid(s: string): number {
let scroe = 0, ans = 0
for (const c of s) {
scroe += c == '(' ? 1 : -1
if (scroe < 0) {scroe = 0; ans++}
}
return ans + scroe
};Python 代码：
class Solution:
def minAddToMakeValid(self, s: str) -> int:
score, ans = 0, 0
for c in s:
score += 1 if c == '(' else -1
if score < 0:
score = 0
ans += 1
return ans + score- 工夫复杂度：$O(n)$
- 空间复杂度：应用
charAt代替toCharArray操作，复杂度为 $O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.921 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
正文完
