Leecode 301. 删除无效的括号——Leecode每日一题系列

缺乏、安全感 2022-08-28 01:43 195阅读 0赞

## 题目描述 ##

> 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。  
>   
> 返回所有可能的结果。答案可以按 任意顺序 返回。

> 示例 1：  
> 输入：s = “()())()”  
> 输出：\["(())()","()()()"\]

> 示例 2：  
> 输入：s = “(a)())()”  
> 输出：\["(a())()","(a)()()"\]

> 示例 3：  
> 输入：s = “)(”  
> 输出：\[""\]

> 提示：  
> 1 <= s.length <= 25  
> s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成  
> s 中至多含 20 个括号

--------------------

简单的DFS回溯，每个括号有删和不删两种状态，遍历即可， 如想优化可加剪枝。

--------------------

class Solution {
        
    private: 
        vector<string> ans;
        unordered_set<string>un;
    public:
        // 这里判断合法时，并不仅仅统计左右括号数是否相等，而是统计左括号在左侧而右括号在右侧
        bool judge(string str) {
        
            int count = 0;
            for (char c : str) {
        
                if (c == '(') {
        
                    count++;
                } else if (c == ')') {
        
                    count--;
                    if (count < 0) {
        
                        return false;
                    }
                }
            }
            return count == 0;
        }
    
        vector<string> removeInvalidParentheses(string s) {
        
            int left = 0, right = 0;
            // 找出不合法的左右括号数
            for (int i = 0; i < s.length(); i++) {
        
                if (s[i] == '(') {
        
                    left++;
                } else if (s[i] == ')') {
        
                    if (left > 0) left--;
                    else right++;
                }
            }
            // 进行回溯
            dfs(s, 0, left, right);
            for(auto i : un) {
        
                ans.push_back(i);
            }
            return ans;
        }
    
        void dfs(string s, int index, int left, int right) {
        
            // 终止条件
            if (left == 0 && right == 0) {
        
                if (judge(s)) {
        
                    un.insert(s);
                    return;
                }
            }
            int len = s.length();
            for (int i = index; i < len; i++) {
        
                // 删除左括号
                if (left > 0 && s[i] == '(') {
        
                    dfs(s.substr(0, i) + s.substr(i + 1, len - i - 1), i, left -1, right);
                }
                // 删除右括号
                if (right > 0 && s[i] == ')') {
        
                    dfs(s.substr(0, i) + s.substr(i + 1, len - i - 1), i, left, right - 1);
                }
            }
        }
    };