问题描述：s="(a)(b)))"，通过移除最少量的括号，使得该字符串为合法的字符串，即括号要配对。
首先我们要有一个判断该字符串是否是合法的函数：
def isvalid(s): count=0 for i in s: #若是左括号，则count加1 if i=="(": count+=1 elif i==")": #如果是右括号，那么count减1，当count<0时，则直接返回不合法 count-=1 if count<0: return False return count==0
然后，对于不合法的的字符串，我们进行遍历，然后遇到“(”或者")"，我们就删除它，将删除后的字符串加入到队列中，以此类推；
def bfs(s): #保存结果 res=[] #存储字符串 queue=[s] #bfs while len(queue)>0: for i in range(len(queue)): if isvalid(queue[i]): res.append(queue[i]) if len(res)>0: return list(set(res)) tmp=[] for t in queue: for i in range(len(t)): if t[i]=="(" or t[i]==")": tmp.append(t[:i]+t[i+1:]) queue=list(set(tmp)) #queue:[‘a)(b))()‘, ‘(a)b))()‘, ‘(a)(b))(‘, ‘(a(b))()‘, ‘(a)(b)()‘, ‘(a)(b)))‘] return list(set(res)) 最后输出：[‘(a(b))()‘, ‘(a)(b)()‘]
原文：https://www.cnblogs.com/xiximayou/p/11657066.html