题目

301. 删除无效的括号【困难】

题解

回溯+剪枝

使用回溯算法，尝试遍历所有可能的去掉非法括号的方案

利用括号匹配的规则求出s中最少需要去掉多少左括号和多少右括号
-> 在原字符串中去掉lremove个左括号和rrmove个右括号
-> 检测剩余字符串是否合法匹配，如果匹配则认为该字符串为可能的结果

对于字符串是否合法，

class Solution {List<String>res=new ArrayList<>();public List<String> removeInvalidParentheses(String s) {int n=s.length();//统计需要删除左右括号的数目int lremove=0,rremove=0;for(int i=0;i<n;i++){char ch=s.charAt(i);if(ch=='(')lremove++;else if(ch==')'){if(lremove==0)rremove++;elselremove--;}}dfs(s,0,lremove,rremove);return res;}public void dfs(String s,int start,int lremove,int rremove){if(lremove==0&&rremove==0){if(isValid(s))res.add(s);return;}int n=s.length();for(int i=start;i<n;i++){//如果遇到连续相同的括号我们只需要搜索一次即可if(i>start&&s.charAt(i)==s.charAt(i-1))continue;//剪枝:剩余字符无法满足去除括号数的要求if(lremove+rremove>n-i)return;//不要这个左括号if(s.charAt(i)=='('&&lremove>0)dfs(s.substring(0,i)+s.substring(i+1,n),i,lremove-1,rremove);//不要这个右括号if(s.charAt(i)==')'&&rremove>0)dfs(s.substring(0,i)+s.substring(i+1,n),i,lremove,rremove-1);}}//判断str中括号是否合法public boolean isValid(String str){int left=0;for(int i=0;i<str.length();i++){char ch=str.charAt(i);if(ch=='(')left++;else if(ch==')'){if(left==0)return false;elseleft--;}}return left==0;//左右括号数目一样，则判断为合法}
}

时间复杂度：$O(n\ast 2^n)$，一个字符串最多可能$2^n$个子序列，每个子序列需要一次合法检测

空间复杂度：$O(n^2)$，每次递归调用需要复制字符串一次