首页 > 代码库 > 301. Remove Invalid Parentheses
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 ).
Examples:
"()())()" -> ["()()()", "(())()"]"(a)())()" -> ["(a)()()", "(a())()"]")(" -> [""]
这题好麻烦。。。基本参考了discussion解法。ref:https://discuss.leetcode.com/topic/28827/share-my-java-bfs-solution
整体思路：bfs，每一层都尝试删除一个符号。如果valid就输出并且从这一层跳出。因此用一个found的boolean来判断这层是不是已经有了。如果没有这个boolean会一直搜索到以下层，
然而题目要求是min，所以没有必要。用一个set来存要检查的避免重复，类似月（（）），删除重复的检查没有必要。还要构建一个isvalid辅助method来解决。
总之好麻烦。。。。理解思路即可吧。public class Solution { public List<String> removeInvalidParentheses(String s) { List<String> res=new ArrayList<String>(); if(s==null) { return res; } Queue<String> check=new LinkedList<>(); Set<String> check2=new HashSet<String>(); check.offer(s); check2.add(s); boolean found=false; while(!check.isEmpty()) { s=check.poll(); if(isValid(s)) { res.add(s); found=true; } if(found) { continue; } for(int i=0;i<s.length();i++) { char pa=s.charAt(i); if(pa==‘(‘||pa==‘)‘) { String another=s.substring(0,i)+s.substring(i+1); if(!check2.contains(another)) { check.offer(another); check2.add(another); } } } } return res; } public boolean isValid(String s) { int count=0; for(int i=0;i<s.length();i++) { if(s.charAt(i)==‘(‘) { count++; } if(s.charAt(i)==‘)‘) { count--; } if(count<0) { return false; } } if(count==0) { return true; } else { return false; } }}
301. Remove Invalid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。