BFS
2018-02-12 本文已影响0人
gyDBD
#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
