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 ).

Example 1:

Input: "()())()"

Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"

Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("

Output: [""]

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

一看“匹配”就以为要用stack：果然很麻烦

用bfs: 随着index i 的增加，括号元素可以加也可以不加在sb.append中体现，所以用dfs

［英文数据结构或算法，为什么不用别的数据结构或算法］：

hashset：dfs是随机的可能出现重复现象，所以用来给结果去重

dfs的格式：

dfs(起点变量，终点变量，过程变量)

［一句话思路］：

为了去除的括号数量最少，只要左右相等就可以所以用L R来控制dfs递增的次数

只能右消左（），不能左消右）（。因为是反的。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

主函数中调用R L要带入字母，不是0
DFS中不需要写for，每次只对一个变量进行处理

［二刷］：

i == length必定会退出，指标为0才添加到答案中

刚新建就被返回了，此时可以return 二合一

［三刷］：

DFS的顺序是左括号先不用，再用先按照初始值来。虽然不知道为什么。

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

选择括号要不要可以用DFS

［复杂度］：Time complexity: O(2^n) Space complexity: O(n)

［算法思想：递归/分治/贪心］：递归

［关键模板化代码］：

［其他解法］：

BFS可是慢啊

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

class Solution {

    public List<String> removeInvalidParentheses(String s) {

        //ini: count L, R. Set, List<String>

        int L = 0, R = 0, n = s.length();

        Set<String> set = new HashSet<>();

        for (int i = 0; i < n; i++) {

            if (s.charAt(i) == '(') L++;

            else if (s.charAt(i) == ')') {

                if (L > 0) L--;

                else R++;

            }

        }

        System.out.println("L =" + L);

        System.out.println("R =" + R);

        //dfs

        dfs(s, 0, set, new StringBuilder(), L, R, 0);

        //return res

        return new ArrayList<String>(set);

        }

    public void dfs(String s, int i, Set<String> set, StringBuilder sb, int L, int R, int open) {

        //cc: exit

        if (L < 0 || R < 0 || open < 0) return ;

        //normal return

        if (i == s.length()) {

            if (L == 0 && R == 0 && open == 0) set.add(sb.toString());

            return ;

        }

            //getlen of sb

            int len = sb.length();

            char c = s.charAt(i);

            if (c == '(') {

            //not use (

            dfs(s, i + 1, set, sb, L - 1, R, open);

            //use (

            dfs(s, i + 1, set, sb.append(c), L, R, open + 1);

            }else if (c == ')') {

            //not use )

            dfs(s, i + 1, set, sb, L, R - 1, open);

            //use )

            dfs(s, i + 1, set, sb.append(c), L, R, open - 1);

            }else {

            dfs(s, i + 1, set, sb.append(c), L, R, open);

            }

            //set len for sb

            sb.setLength(len);

    }

    }

[是否头一次写此类driver funcion的代码] ：

巴特西

301. Remove Invalid Parentheses去除不符合匹配规则的括号

最新文章

热门文章