本文共 1920 字，大约阅读时间需要 6 分钟。

题目：（中等）

标签：字符串、栈

解法一（栈）：

class Solution:    def minInsertions(self, s: str) -> int:        # 用栈处理可以配对的括号        N = len(s)        ans = 0        stack = []        i = 0        while i < N:            if s[i] == "(":                stack.append("(")                i += 1            else:                if i < len(s) - 1 and s[i + 1] == ")":                    i += 2                else:  # 如果不是连续的括号则补一个使其成为连续的括号                    i += 1                    ans += 1                if stack and stack[-1] == "(":                    stack.pop()                else:                    stack.append(")")        print(ans, stack)        # 处理未配对的括号        n1 = stack.count("(")        n2 = len(stack) - n1        ans += n1 * 2        ans += n2        return ans

解法二（优化解法一）：

class Solution:    def minInsertions(self, s: str) -> int:        N = len(s)        ans = 0        left_num = 0        i = 0        while i < N:            if s[i] == "(":                left_num += 1                i += 1            else:                if i < len(s) - 1 and s[i + 1] == ")":                    i += 2                else:  # 如果不是连续的括号则补一个使其成为连续的括号                    i += 1                    ans += 1                if left_num > 0:                    left_num -= 1                else:                    ans += 1        return ans + 2 * left_num

解法三（字符串替换）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F9UJhajN-1599007267137)(LeetCode题解(1541)]：截图.png)

class Solution:    def minInsertions(self, s: str) -> int:        s = s.replace("))", "*")        ans = s.count(")")        s = s.replace(")", "*")        while len(ss := s.replace("(*", "")) != len(s):            s = ss        return ans + len(s) + s.count("(")

转载地址：https://dataartist.blog.csdn.net/article/details/108354983 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！