301. Remove Invalid Parenthesis

lentoo 發布于2019-08-14 14:17 / 2398人閱讀

摘要：問題解答這題是看里面的的代碼如果比大或等的話，就繼續掃下去否則，我們就找到當前有可能刪去的，然后刪掉看新的如果只從左到右掃了，還是的時候，我們還要再從右往左掃一遍否則兩遍都掃完了，就加入結果中去

問題：
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;
}

GPU云服務器云服務器 Parenthesis invalid remove invalid argument

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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