数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python中使括号有效所需的最小添加
假设我们有一个包含 '(' 和 ')' 括号的字符串 S，我们需要在任意位置添加最少的括号，以便生成的括号字符串有效。当且仅当满足以下条件时，括号字符串才有效：
- 它是空字符串
- 它可以写成 XY（X 与 Y 连接），其中 X 和 Y 是有效的字符串
- 它可以写成 (A)，其中 A 是一个有效的字符串。
因此，如果字符串类似于 "()))((", 则我们需要添加 4 个括号才能使字符串有效。
为了解决这个问题，我们将遵循以下步骤：
- 如果 S 为空，则返回 0
- 计数器 count := 0，temp 为一个数组，临时计数器 temp_counter := 0
- 对于 S 中的每个 i
- 如果 i 是左括号，则将 i 插入 temp
- 否则
- 当 temp 的长度 > 0 且最后一个元素是左括号时，删除 temp 的最后一个元素，否则将 i 插入 temp
- 返回 temp 的大小。
让我们看看下面的实现，以便更好地理解：
示例
class Solution:
def minAddToMakeValid(self, S):
if not S:
return 0
count = 0
temp = []
temp_counter = 0
for i in S:
if i =='(':
temp.append(i)
else:
if len(temp)>0 and temp[len(temp)-1] =='(':
temp.pop(len(temp)-1)
else:
temp.append(i)
return len(temp)
ob = Solution()
print(ob.minAddToMakeValid("()))(("))输入
"()))(("输出
4
更新于：2020年4月30日
浏览量 338
广告