LeetCode301——删除无效的括号

怼烎@ 2022-01-23 01:41 392阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/remove-invalid-parentheses/][https_leetcode-cn.com_problems_remove-invalid-parentheses]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：回溯

### 思路一：回溯法（用栈来判断括号是否匹配） ###

由于没有任何剪枝操作，该回溯过程穷举了所有可能的情形，时间复杂度是O(2 ^ n)，其中n为括号个数。空间复杂度是O(m)，其中m为字符串的长度。

JAVA代码：

public class Solution {
    
        private Set<String> set;
    
        private String input;
    
        private int maxLen = 0;
    
        public List<String> removeInvalidParentheses(String s) {
            set = new HashSet<>();
            input = s;
            removeInvalidParentheses(0, "", new LinkedList<>());
            return new ArrayList<>(set);
        }
    
        private void removeInvalidParentheses(int index, String valid, LinkedList<Character> linkedList) {
            if (index == input.length()) {
                if (linkedList.isEmpty()) {
                    if (maxLen < valid.length()) {
                        maxLen = valid.length();
                        set.clear();
                        set.add(valid);
                    } else if (maxLen == valid.length()) {
                        set.add(valid);
                    }
                }
                return;
            }
            char c = input.charAt(index);
            if (c == '(') {
                removeInvalidParentheses(index + 1, valid, new LinkedList<>(linkedList));
                linkedList.push(c);
                removeInvalidParentheses(index + 1, valid + c, linkedList);
            } else if (c == ')') {
                if (linkedList.isEmpty()) {
                    removeInvalidParentheses(index + 1, valid, linkedList);
                } else {
                    removeInvalidParentheses(index + 1, valid, new LinkedList<>(linkedList));
                    linkedList.pop();
                    removeInvalidParentheses(index + 1, valid + c, linkedList);
                }
            } else {
                removeInvalidParentheses(index + 1, valid + c, linkedList);
            }
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1][]

### 思路二：回溯法（用左括号的数量和右括号的数量来判断是否是有效字符串） ###

时间复杂度是O(2 ^ n)，其中n为括号个数。空间复杂度是O(m)，其中m为字符串的长度。但少了思路一中的入栈和出栈操作，因此速度上会有所提升。

JAVA代码：

public class Solution {
    
        private Set<String> set;
    
        private String input;
    
        private int maxLen = 0;
    
        public List<String> removeInvalidParentheses(String s) {
            set = new HashSet<>();
            input = s;
            removeInvalidParentheses(0, "", 0, 0);
            return new ArrayList<>(set);
        }
    
        private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount) {
            if (leftCount < rightCount) {
                return;
            }
            if (index == input.length()) {
                if (leftCount == rightCount) {
                    if (maxLen < valid.length()) {
                        maxLen = valid.length();
                        set.clear();
                        set.add(valid);
                    } else if (maxLen == valid.length()) {
                        set.add(valid);
                    }
                }
                return;
            }
            char c = input.charAt(index);
            if (c == '(') {
                removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
                removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount);
            } else if (c == ')') {
                removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1);
            } else {
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount);
            }
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 2][]

### 思路三：回溯（带剪枝操作） ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 3][]

如上图所示，Solution1和Solution2的结果可以由很多种回溯过程得到，这些回溯过程对于我们来说其实是多余的，因为得到的是完全相同的结果。对比上图中的6种解决方案，我们发现需要删除的左括号数都是2个，需要删除的右括号数都是0个。事实上，只要题目给出了相应的字符串，我们就能确定需要删除的左括号个数和右括号个数，使得删除的总括号数最少。

一旦确定了需要删除的左括号个数和右括号个数，我们的回溯过程就能大大简化。

**递归出口**：

在递归遍历完字符串之后，只要满足需要删除的左括号个数和右括号个数均为0，该结果就是满足条件的一个答案。

**递归过程**：

（1）如果当前字符是左括号，如果需要删除的左括号个数leftRem大于0，可以考虑忽略该左括号。当然，还有一种情形是不忽略该左括号。

（2）如果当前字符是右括号，如果需要删除的右括号个数rightRem大于0，可以考虑忽略该右括号。当然，还有一种情形——当左括号个数leftCount大于右括号个数rightCount时，不忽略该右括号。

（3）如果当前字符既不是左括号也不是右括号，直接将该字符加进结果即可。

时间复杂度在最坏情况下依然是O(2 ^ n)，其中n为括号的数量。空间复杂度是O(m)，其中m为字符串的长度。

JAVA代码：

public class Solution {
    
        private Set<String> set;
    
        private String input;
    
        public List<String> removeInvalidParentheses(String s) {
            set = new HashSet<>();
            input = s;
            int left = 0, right = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    left++;
                } else if (c == ')') {
                    if (left == 0) {
                        right++;
                    } else {
                        left--;
                    }
                }
            }
            removeInvalidParentheses(0, "", 0, 0, left, right);
            return new ArrayList<>(set);
        }
    
        private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount, int leftRem, int rightRem) {
            if (index == input.length()) {
                if (leftRem == 0 && rightRem == 0) {
                    set.add(valid);
                }
                return;
            }
            char c = input.charAt(index);
            if (c == '(') {
                if (leftRem > 0) {
                    removeInvalidParentheses(index + 1, valid, leftCount, rightCount, leftRem - 1, rightRem);
                }
                removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount, leftRem, rightRem);
            } else if (c == ')') {
                if (rightRem > 0) {
                    removeInvalidParentheses(index + 1, valid, leftCount, rightCount, leftRem, rightRem - 1);
                }
                if (rightCount < leftCount) {
                    removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1, leftRem, rightRem);
                }
            } else {
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount, leftRem, rightRem);
            }
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 4][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_remove-invalid-parentheses]: https://leetcode-cn.com/problems/remove-invalid-parentheses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220123/7be29cf0a78d415dabeac05e8b4e4d68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1]: /images/20220123/a0a897d8e9a546f89dc276db18045b0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 2]: /images/20220123/89a0047f34f54055bf94f9e9b067110f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 3]: /images/20220123/1615c9ac18c64ac6bb39d455dcc79ea3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 4]: /images/20220123/9fd7fa2bb0f9444d8620ca4b6b560b39.png