关于后端:921-使括号有效的最少添加-简单成对括号问题

题目形容

这是 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 多平台公布