广度优先遍历--合法的括号

概述广度优先遍历

问题描述：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    

然后，对于不合法的的字符串，我们进行遍历，然后遇到“(”或者")"，我们就删除它，将删除后的字符串加入到队列中，以此类推；

 bfs(s):    保存结果    res=[]    存储字符串    queue=[s]    bfs    while len(queue)>0:         range(len(queue)):            if isvalID(queue[i]):                res.append(queue[i])        if len(res)>0:             List(set(res))        tmp=[]        for t  queue:             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)))']     List(set(res))最后输出：['(a(b))()',(a)(b)()']

 

总结

以上是内存溢出为你收集整理的广度优先遍历--合法的括号全部内容，希望文章能够帮你解决广度优先遍历--合法的括号所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。