本文共 2074 字，大约阅读时间需要 6 分钟。

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: “()())()”

输出: ["()()()", “(())()”]

示例 2:

输入: “(a)())()”

输出: ["(a)()()", “(a())()”]

示例 3:

输入: “)(”

输出: [""]

回溯算法：

递归的状态现在由五个不同的变量定义：

• 1.index它表示我们必须在原始字符串中处理的当前字符。
• 2.left_count它表示添加到为我们正在构建的表达式中的左括号数
• 3.right_count它表示添加到我们正在构建的表达式中的右括号数
• 4.left_rem是要要删除的左括号数
• 5.right_rem表示保留要删除的右括号数。总的来说，为了使最终表达式有效，left_rem==0和right_rem==0.
• 当我们决定不考虑括号时，即删除括号，不管是左括号还是右括号，我们也必须考虑它们相应的剩余计数。这意味着，如果left_rem>0，我们只能放弃左括号；同样，对于右括号，我们将检查right_rem>0.
• 检查括号没有变化。只有丢弃圆括号的条件才会改变
• 表达式再基本情况下有效的条件现在将变为left_rem0 and right_rem0。注意，我们不必再检查left_count==right_count了，因为在有效表达式的情况下，在递归结束时，我们会删除所有放错位置或无效的括号。所以，只有当left_rem==0 and right_rem==0时，我们才需要检查。

class Solution {
   		private Set
   
     validExpressions = new HashSet
    
     ();			    public List
     
       removeInvalidParentheses(String s) {
   	    	// 记录	    	int left = 0, right = 0;	    		    	// 开始遍历	    	for(int i=0;i
      
       0?left-1:left;	    		}	    	}	    		    	this.recurse(s,0,0,0,left,right,new StringBuilder());	    	return new ArrayList
       
        (this.validExpressions);	    }	    	    private void recurse(	    		String s,	    		int index,	    		int leftCount,	    		int rightCount,	    		int leftRem,	    		int rigtRem,	    		StringBuilder expression) {
   	    		    	if(index == s.length()) {
   	    		if(leftRem==0&&rigtRem==0) {
   	    			this.validExpressions.add(expression.toString());	    		}	    	}else {
       			char character = s.charAt(index);    			int  length = expression.length();    			    			if((character=='(' && leftRem>0) || (character==')'&&rigtRem>0)) {
       				this.recurse(s, index+1, leftCount, rightCount, leftRem-(character=='('?1:0), rigtRem-(character==')'?1:0), expression);    			}    			    			expression.append(character);    			    			if(character!='('&&character!=')') {
       				this.recurse(s, index+1, leftCount, rightCount, leftRem, rigtRem, expression);    			}else if(character=='(') {
       				this.recurse(s, index+1, leftCount+1, rightCount, leftRem, rigtRem, expression);    			}else if(rightCount
       
      
     
    
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111655979 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！