- 标签:栈、字符串
- 难度:简单
描述:有效括号字符串为空 ""
、"("
+ ")"
或
- 例如,
""
,"()"
,"(())()"
和"(()(()))"
都是有效的括号字符串。
如果有效字符串
给定一个非空有效字符串
要求:对
说明:
-
$1 \le s.length \le 10^5$ 。 -
$s[i]$ 为'('
或')'
。 -
$s$ 是一个有效括号字符串。
示例:
- 示例 1:
输入:s = "(()())(())"
输出:"()()()"
解释:
输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())",
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
- 示例 2:
输入:s = "(()())(())(()(()))"
输出:"()()()()(())"
解释:
输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))",
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
题目要求我们对
通过观察可以发现,每个原语其实就是一组有效的括号对(左右括号匹配时),此时我们需要删除这组有效括号对的最外层括号。
我们可以使用一个计数器
当计数器遇到左括号时,令计数器
为了删除每个原语的最外层括号,当遇到每个原语最外侧的左括号时(此时
同理,当遇到每个原语最外侧的右括号时(此时
具体步骤如下:
- 遍历字符串
$s$ 。 - 如果遇到
'('
,判断当前计数器是否大于$0$ :- 如果
$cnt > 0$ ,则将'('
存入答案字符串中,并令计数器加$1$ ,即:cnt += 1
。 - 如果
$cnt == 0$ ,则令计数器加$1$ ,即:cnt += 1
。
- 如果
- 如果遇到
')'
,判断当前计数器是否大于$1$ :- 如果
$cnt > 1$ ,则将')'
存入答案字符串中,并令计数器减$1$ ,即:cnt -= 1
。 - 如果
$cnt == 1$ ,则令计数器减$1$ ,即:cnt -= 1
。
- 如果
- 遍历完返回答案字符串
$ans$ 。
class Solution:
def removeOuterParentheses(self, s: str) -> str:
cnt, ans = 0, ""
for ch in s:
if ch == '(':
if cnt > 0:
ans += ch
cnt += 1
else:
if cnt > 1:
ans += ch
cnt -= 1
return ans
-
时间复杂度:$O(n)$,其中
$n$ 为字符串$s$ 的长度。 - 空间复杂度:$O(n)$。