301. Remove Invalid Parenthesis

lentoo 发布于2019-08-14 14:17 / 2222人阅读

摘要：问题解答这题是看里面的的代码如果比大或等的话，就继续扫下去否则，我们就找到当前有可能删去的，然后删掉看新的如果只从左到右扫了，还是的时候，我们还要再从右往左扫一遍否则两遍都扫完了，就加入结果中去

问题：
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 ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

解答：
这题是看discuss里面的dietpanda的代码：

public void remove(String s, List result, int last_i, int last_j, char[] par) {
    for (int stack = 0, i = last_i; i < s.length(); i++) {
        if (s.charAt(i) == par[0]) stack++;
        if (s.charAt(i) == par[1]) stack--;
        //如果"("比")"大或等的话，就继续扫下去
        if (stack >= 0) continue;
        //否则，我们就找到当前有可能删去的")"，然后删掉看新的string
        for (int j = last_j; j <= i; j++) {
            if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1])) {
                remove(s.substring(0, j) + s.substring(j + 1, s.length()), result, i, j, par);
            }
        }
        return;
    }
    
    String reversed = new StringBuilder(s).reverse().toString();
    //如果只从左到右扫了，par[0]还是"("的时候，我们还要再从右往左扫一遍
    if (par[0] == "(") {
        remove(reversed, result, 0, 0, new char[]{")", "("});
    } else {
        //否则两遍都扫完了，就加入结果中去
        result.add(reversed);
    }
}

public List removeInvalidParentheses(String s) {
    List result = new ArrayList();
    remove(s, result, 0, 0, new char[]{"(", ")"});
    return result;
}

云服务器私有云 Parenthesis invalid remove invalid argument

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64920.html

leetcode 301. Remove Invalid Parentheses

摘要：一个合法的字符串是指左括号和右括号必定成对出现。要求得出用最少次数的删除可以得到的所有的合法字符串。最后两个结果重复，因此只保留，两个结果。最终生成的合法字符串为。方法相同于上一种情况。其中出现了两次。在该下标前的删除将会产生重复的结果。题目要求 Remove the minimum number of invalid parentheses in order to make the...

zhisheng 2019-08-15 14:41 评论0 收藏0
[LeetCode] 678. Valid Parenthesis String

Problem Given a string containing only three types of characters: (, ) and *, write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parent...

dinfer 2019-08-16 13:42 评论0 收藏0
[LeetCode] 606. Construct String from Binary Tree

Problem You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair (). And...

madthumb 2019-08-16 13:39 评论0 收藏0
LeetCode 606. Construct String from Binary Tree 二叉

摘要：题意从一颗二叉树转为带括号的字符串。这题是的姊妹题型，该题目的解法在这里解法。 LeetCode 606. Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder t...

mikyou 2019-08-16 13:31 评论0 收藏0
LeetCode 536. Construct Binary Tree from String 从带

摘要：题意从一个带括号的字符串，构建一颗二叉树。其中当而时，展示为一个空的括号。同时要考虑负数的情况，所以在取数字的时候，必须注意所在位置。遇到则从栈中出元素。最后中的元素就是，返回栈顶元素即可。 LeetCode 536. Construct Binary Tree from String You need to construct a binary tree from a string ...

tabalt 2019-08-16 13:31 评论0 收藏0