class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
}
};
301. 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s 由小写英文字母以及括号 '(' 和 ')' 组成s 中至多含 20 个括号相似题目
原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 6.3 MB, 提交时间: 2023-06-06 09:56:35
func isValid(str string) bool {
cnt := 0
for _, ch := range str {
if ch == '(' {
cnt++
} else if ch == ')' {
cnt--
if cnt < 0 {
return false
}
}
}
return cnt == 0
}
func removeInvalidParentheses(s string) (ans []string) {
curSet := map[string]struct{}{s: {}}
for {
for str := range curSet {
if isValid(str) {
ans = append(ans, str)
}
}
if len(ans) > 0 {
return
}
nextSet := map[string]struct{}{}
for str := range curSet {
for i, ch := range str {
if i > 0 && byte(ch) == str[i-1] {
continue
}
if ch == '(' || ch == ')' {
nextSet[str[:i]+str[i+1:]] = struct{}{}
}
}
}
curSet = nextSet
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-06-06 09:56:18
func isValid(str string) bool {
cnt := 0
for _, ch := range str {
if ch == '(' {
cnt++
} else if ch == ')' {
cnt--
if cnt < 0 {
return false
}
}
}
return cnt == 0
}
func helper(ans *[]string, str string, start, lremove, rremove int) {
if lremove == 0 && rremove == 0 {
if isValid(str) {
*ans = append(*ans, str)
}
return
}
for i := start; i < len(str); i++ {
if i != start && str[i] == str[i-1] {
continue
}
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if lremove+rremove > len(str)-i {
return
}
// 尝试去掉一个左括号
if lremove > 0 && str[i] == '(' {
helper(ans, str[:i]+str[i+1:], i, lremove-1, rremove)
}
// 尝试去掉一个右括号
if rremove > 0 && str[i] == ')' {
helper(ans, str[:i]+str[i+1:], i, lremove, rremove-1)
}
}
}
func removeInvalidParentheses(s string) (ans []string) {
lremove, rremove := 0, 0
for _, ch := range s {
if ch == '(' {
lremove++
} else if ch == ')' {
if lremove == 0 {
rremove++
} else {
lremove--
}
}
}
helper(&ans, s, 0, lremove, rremove)
return
}
python3 解法, 执行用时: 132 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-06 09:55:48
class Solution:
def removeInvalidParentheses(self, s:str) -> List[str]:
def isValid(s:str)->bool:
cnt = 0
for c in s:
if c == "(": cnt += 1
elif c == ")": cnt -= 1
if cnt < 0: return False # 只用中途cnt出现了负值，你就要终止循环，已经出现非法字符了
return cnt == 0
# BFS
level = {s} # 用set避免重复
while True:
valid = list(filter(isValid, level)) # 所有合法字符都筛选出来
if valid: return valid # 如果当前valid是非空的，说明已经有合法的产生了
# 下一层level
next_level = set()
for item in level:
for i in range(len(item)):
if item[i] in "()": # 如果item[i]这个char是个括号就删了，如果不是括号就留着
next_level.add(item[:i]+item[i+1:])
level = next_level
python3 解法, 执行用时: 2052 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-06 09:55:20
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
res_length = -1 # 记录删除最小数量的无效括号的长度
st = [] # 判断括号合法性的栈，用于剪枝
ans = set() # 记录答案（因为会重复所以要使用set来存储）
path = [] # 记录回溯路径
n = len(s)
def dfs(i: int) -> int:
if i == len(s):
if st == []:
nonlocal res_length
if res_length == -1:
# 只有第一次执行到此时才会更新res_length的值
res_length = len(path)
if len(path) == res_length:
ans.add(''.join(path))
return
# 剪枝
if n - i + len(path) < res_length:
return
# 小写字母一定选 与st无关
if s[i] not in '()':
path.append(s[i])
dfs(i + 1)
path.pop()
else:
# 选
path.append(s[i]) # 记录路径
if s[i] == '(':
st.append(s[i]) # '(' 入栈
dfs(i + 1)
st.pop() # 恢复现场
elif s[i] == ')' and st:
last = st.pop() # ')' 出栈
dfs(i + 1)
st.append(last) # 恢复现场
path.pop() # 恢复现场
# 不选
dfs(i + 1)
dfs(0) # 回溯入口
return list(ans)