Skip to content

Latest commit

 

History

History
214 lines (168 loc) · 6.35 KB

File metadata and controls

214 lines (168 loc) · 6.35 KB

English Version

题目描述

给你一个括号字符串 s ,它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足:

  • 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
  • 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())", "())(())))" 和 "(())())))" 都是平衡的, ")()", "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

 

示例 1:

输入:s = "(()))"
输出:1
解释:第二个左括号有与之匹配的两个右括号,但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

示例 2:

输入:s = "())"
输出:0
解释:字符串已经平衡了。

示例 3:

输入:s = "))())("
输出:3
解释:添加 '(' 去匹配最开头的 '))' ,然后添加 '))' 去匹配最后一个 '(' 。

示例 4:

输入:s = "(((((("
输出:12
解释:添加 12 个 ')' 得到平衡字符串。

示例 5:

输入:s = ")))))))"
输出:5
解释:在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ,字符串变成平衡字符串 "(((())))))))" 。

 

提示:

  • 1 <= s.length <= 10^5
  • s 只包含 '(' 和 ')' 。

解法

方法一:贪心

我们用 $x$ 表示字符串中待匹配的左括号的数量,初始时为 $0$。遍历字符串 $s$

如果遇到左括号,则 $x$ 的值加 $1$;如果遇到右括号,我们分情况讨论:

  • 如果有两个连续的右括号,那么我们先让指针往后移动一位;否则,我们需要插入一个右括号,使得出现两个连续的右括号,因此插入次数加 $1$
  • 如果 $x = 0$,说明当前没有待匹配的左括号,我们需要插入一个左括号,用于匹配上面准备好的两个连续的右括号,因此插入次数加 $1$;否则,我们让 $x$ 的值减 $1$

然后指针往后移动一位,继续下一次遍历。

遍历结束后,如果 $x = 0$,说明字符串已经平衡,返回插入次数;否则,说明字符串中有待匹配的左括号,我们需要再插入 $2 \times x$ 个右括号,使得字符串变成平衡字符串,返回插入次数。

时间复杂度 $O(n)$,空间复杂度 $O(1)$

Python3

class Solution:
    def minInsertions(self, s: str) -> int:
        ans = x = 0
        i, n = 0, len(s)
        while i < n:
            if s[i] == '(':
                # 待匹配的左括号加 1
                x += 1
            else:
                if i < n - 1 and s[i + 1] == ')':
                    # 有连续两个右括号,i 往后移动
                    i += 1
                else:
                    # 只有一个右括号,插入一个
                    ans += 1
                if x == 0:
                    # 无待匹配的左括号,插入一个
                    ans += 1
                else:
                    # 待匹配的左括号减 1
                    x -= 1
            i += 1
        # 遍历结束,仍有待匹配的左括号,说明右括号不足,插入 x << 1 个
        ans += x << 1
        return ans

Java

class Solution {
    public int minInsertions(String s) {
        int ans = 0, x = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '(') {
                ++x;
            } else {
                if (i < n - 1 && s.charAt(i + 1) == ')') {
                    ++i;
                } else {
                    ++ans;
                }
                if (x == 0) {
                    ++ans;
                } else {
                    --x;
                }
            }
        }
        ans += x << 1;
        return ans;
    }
}

C++

class Solution {
public:
    int minInsertions(string s) {
        int ans = 0, x = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                ++x;
            } else {
                if (i < n - 1 && s[i + 1] == ')') {
                    ++i;
                } else {
                    ++ans;
                }
                if (x == 0) {
                    ++ans;
                } else {
                    --x;
                }
            }
        }
        ans += x << 1;
        return ans;
    }
};

Go

func minInsertions(s string) int {
	ans, x, n := 0, 0, len(s)
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			x++
		} else {
			if i < n-1 && s[i+1] == ')' {
				i++
			} else {
				ans++
			}
			if x == 0 {
				ans++
			} else {
				x--
			}
		}
	}
	ans += x << 1
	return ans
}

...