合法的括号

• 简介
  • 比较基础的BFS题目。
  • 注意，由于要对不合法的字符串最小步数删减为合法的字符串，所以BFS合适。
  • 之所以选择BFS，是因为要返回的结果为删减最小数目的括号后使字符串合法，“就近搜索显然合适”。
• 问题描述
  • 给定一个字符串，字符串会出现字母和"(“以及”)"，认为左右括号匹配完全的字符串是合法的，不完全的通过删除若干个括号得到合法字符串，现在要求移除最少数目的括号，使得其合法，并返回所有合法字符串。
• 问题分析
  • 对于括号匹配的问题，最先想到的应该是栈。常规的操作是左括号入栈，遇到右括号将一个左括号出栈。最后栈空，则括号字符串合法。但是，对于最短路径这类题，广度优先遍历不仅可以找到合法字符串数目，还可以找到找到的字符串序列具体情况，所以BFS更加合适一些。
  • 举个例子
    • 假设字符串为"(a)(b))()"，发现右括号有4个，而左括号只有3个，那么我们需要删除一个右括号。
      • 这就是一个核心思路，当左右括号不对等的时候应该删除差值数目的括号使得数目对等，将删除之后合法的加入遍历队列。
      • 删除第一个右括号得到"(a(b))()"，删除第二和第三个右括号得到"(a)(b)()"，删除第四个后不合法。（这里有两个核心问题，判断合法和去重）
  • 首先，如何判断一个字符串是否合法。
    • 当然可以使用之前所说的栈，这毕竟是栈的典型应用。
    • 其实，为了节省内存开销，可以使用一个变量模拟栈，从头到尾扫描字符串，遇到左括号变量加1，遇到右括号变量减1，一旦某一步变量小于0，这个字符串就是非法的；最后变量为0则合法。
    • 代码

      •   def is_valid(s):"""判断是否括号合法:param s: :return: """count = 0for item in s:if item == "(":count += 1elif item == ")":count -= 1if count < 0:return Falsereturn count == 0
        

  • 其次，去重，每一层使用set即可。（不可层间）
  • BFS算法流程
    • 初始化队列为空，将初始字符串加入队列。
    • 每次从队列取出一个字符串，判断是否合法。
      • 如果合法，则加入结果集。（因为此时最小删除步数为0）
      • 如果不合法，找到左右括号的位置，删除其。理论上对于N个括号的字符串，这一步得到N-1个字符串，由于去重，也可能小于这个数目。
      • 注意：每一次对当前队列判断是否存在合法字符串，若这一层存在，则算法结束（因为再去除括号已经不符合最少步数要求）。
  • 这个问题要求去除最少的括号来得到给定字符串的合法的含有括号的字符串，要找到所有合法结果，还要保证去除最少的括号，同时满足这两个条件。
    • 找出所有，通过队列为空来保证。
    • 保证去除最少括号则是发现合法的字符串，就不要搜索了，直接跳出循环，称为剪枝。
• 代码

  •   # -*-coding:utf-8-*-def is_valid(s):"""判断是否括号合法:param s::return:"""count = 0for item in s:if item == "(":count += 1elif item == ")":count -= 1if count < 0:return Falsereturn count == 0def solve(s):res = []queue = []queue.append(s)while len(queue) > 0:# 每次去队列找其中元素，这时队列里面的都是一层的for item in queue:if is_valid(item):res.append(item)if len(res) > 0:# 只有这一层没有合法的，才会继续去除括号向下一层找return list(set(res))temp = []for item in queue:for i in range(len(item)):if item[i] == "(" or item[i] == ")":temp.append(item[:i] + item[i+1:])queue = list(set(temp))return list(set(res))if __name__ == '__main__':print(solve("(a)(b))()"))

• 运行结果
  • 
• 补充说明
  • 具体代码可以查看我的Github，欢迎Star或者Fork
  • 参考书《你也能看得懂的Python算法书》

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！