Article From:https://www.cnblogs.com/sherylwang/p/9688537.html

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

FBUltra-high frequency questions, the meaning of the title is to remove the minimum number of illegal brackets in the input string, making it a legitimate string. Note that there may be other letters in the string.

It is easy to think of using BFS or DFS to remove the least legitimate characters and return many possibilities. The main idea of using BFS to do this is to remove a character from the string in turn to see if it is legal. If it is already legal, it operates on the level of this length, not on the next level.Parenthesis removal. How do you code?

class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if s == "":
return [""]
res = []
self.remove(s, res)
return res

def isParenthese(self, c):
if c == '(' or c == ')':
return True
else:
return False

def isValid(self, s):
cnt = 0
for c in s:
if c == ')':
cnt -= 1
if cnt < 0:
return False
elif c == '(':
cnt += 1
return cnt == 0

def remove(self, s, res):
queue = collections.deque()
queue.append(s)
used = set()
curlevel = False
while queue:
cur = queue.popleft()
if self.isValid(cur):
res.append(cur)
#important curlevel
= True if curlevel: #important， no process next level continue for i in xrange(len(cur)): if self.isParenthese(cur[i]): sub = cur[:i] + cur[i+1:] if sub not in used: queue.append(sub) used.add(sub) return

As you can see, at each level of the bfs, you try to remove a single bracket to determine if it is legal, and if it is, add a string to the result. At the same time, to avoid duplication, a string has been processed before each layer, and then it needs to be avoided and avoided.The emergence of the last repetition result.

Complexity analysis of this solution: worst of all, each layer of the string needs to be processed until finally, each layer is calculated as follows:

1. n*C(n, n)

2.(n-1)*C(n,n-1)

3.(n-2)C(n, n-1)C(n-1, n-2)= (n-2)*C(n, n-2)

By analogy, the final complexity is:

n*C(n, n) + (n-1)*C(n,n-1) + (n-2)*C(n, n-2)+….+1*C(n,1) = n*(C(n-1,n-1)+C(n-1, n-2)+….C(n-1,1)) = n *2^(n-1)