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

发布时间：2020-12-20 09:50:43 所属栏目：Python 来源：网络整理

导读：问题描述：s="(a)(b)))"，通过移除最少量的括号，使得该字符串为合法的字符串，即括号要配对。首先我们要有一个判断该字符串是否是合法的函数： def isvalid(s): count = 0 for i in s: # 若是左括号，则count加1 if i== " ( " : count +=1 elif i== ) : 如

问题描述：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)()']

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!