#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
网友评论