LeetCode 301 Remove Invalid Parentheses

LeetCode

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

Input: s = “()())()”
Output: [“(())()”,”()()()”]

Example 2:

Input: s = “(a)())()”
Output: [“(a())()”,”(a)()()”]

Example 3:

Input: s = “)(“
Output: [“”]

Constraints:

1 <= s.length <= 25 s consists of lowercase English letters and parentheses '(' and ')'.
* There will be at most 20 parentheses in s.

题目大意：

求最小去掉不合法括号数之后的所有结果

算法思路：

最值问题考虑用DP和BFS，DP难以拆分子问题。所以考虑用BFS + 括号是否合法

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题 答案包含上题, BFS

注意事项：

1. 由于()())() -> (())()，所以去掉的括号不一定都不合法，所以BFS要尝试删除每一个括号。若节点合法，加入结果且记录最小删除数，因为要求同一距离下的所有结果，所以用这个最小数来剪枝。
2. 输入含小写字母，所以无论是判断括号是否合法还是生成儿子节点都要跳过
3. 模板中含if neighbor in visited，不能忘记写

Python代码：

def removeInvalidParentheses(self, s: str) -> List[str]:
	queue = collections.deque([s])
	visited = set([s])
	res, min_dis = [], float('inf')
	distance = collections.defaultdict(int)
	while queue:
		node = queue.popleft()
		if self.is_valid(node):
			res.append(node)
			min_dis = min(min_dis, distance[node])
			continue
		if distance[node] > min_dis:
			continue
		for i in range(len(node)):
			if node[i] not in ['(', ')']:  # remember
				continue
			child = node[:i] + node[i + 1:]
			if child in visited: # remember
				continue
			queue.append(child)
			visited.add(child)
			distance[child] = distance[node] + 1
	return res

def is_valid(self, s): # remember not to use get_invalid_index ()())() -> (())()
	stack = []
	for i, char in enumerate(s):
		if char not in ['(', ')']: # remember
			continue
		if char == ')' and stack and s[stack[-1]] == '(':
			stack.pop()
		else:
			stack.append(i)
	return False if stack else True

算法分析：

时间复杂度为O(2n)，空间复杂度O(n)