BFS

作者: gyDBD | 来源:发表于2018-02-12 02:52 被阅读0次

    #hard 301.Remove Invalid Parentheses

    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 ).

    "()())()" -> ["()()()", "(())()"]

    "(a)())()" -> ["(a)()()", "(a())()"]

    ")(" -> [""]

    可以用DFS和BFS

    BFS的思想就是,也是要两个队列的,因为结果中只要求我们减掉最少个数的括号的结果,而不是所有符合括号匹配的结果,所以还是level order traverse

    还要有一个visited来记录这个String是不是已经被我们判断过的,因为判断过的不能重复加入的,从头到尾遍历,如果说是除了左括号右括号的东西,我们都continue,否则我们就可以去掉,然后加入queue然后之后用以判断是否达标。还有就是我们需要去记录,如果这一层一旦有String已经达标了那么我们就continue,不会再往queue里加入下一层的String

    相关文章

      网友评论

          本文标题:BFS

          本文链接:https://www.haomeiwen.com/subject/yzfrtftx.html