LeetCode[22] Generate Parentheses

Jonathan Shieber 發布于2019-08-14 15:02 / 3432人閱讀

摘要：復雜度思路注意的地方，要限制左括號和右括號。每出現一次左括號，就相對于限定了，最多只能出現那么多右括號。所以，為了完成這種限定，用來控制。不然會有的情況出現。

LeetCode[22] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
]

BackTracking

復雜度
O(N!),O(N)

思路
注意trick的地方，要限制左括號和右括號。每出現一次左括號，就相對于限定了，最多只能出現那么多右括號。所以，為了完成這種限定，用right - 1來控制。不然會有“(()))(”的情況出現。

代碼

public List generateParenthesis(int n) {
    List res = new LinkedList<>();
    helper(res, 0, n, n, new StringBuilder());
    return res;
}

public void helper(List res, int left, int right, int n, StringBuilder temp) {
    // Base case;
    if(left == n && right == n) {
        res.add(temp.roString());
    }
    if(left < n) {
        // 限制在當前這么多左括號的情況下，最多只能出現那么多的右括號。
        helper(res, left + 1, right - 1, n, temp.append("("));
        temp.deleteCharAt(temp.length() - 1);
    }
    if(right < n) {
        helper(res, left, right + 1, n, temp.append(")"));
        temp.deleteCharAt(temp.length() - 1);
    }
}

GPU云服務器云服務器 Parentheses Generate LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65249.html

[LeetCode] 22. Generate Parentheses

Problem Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ ((())), (()()), (())(), ()(()), ...

curlyCheng 2019-08-19 11:15 評論0 收藏0
leetcode22. Generate Parentheses

摘要：當右括號和左括號的剩余量均為時，及為一個最終結果。而則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

騫諱護 2019-08-14 18:35 評論0 收藏0
leetcode 22 Generate Parentheses

摘要：要求返回一個中包含組括號所有可能的符合規則的組合。例如輸入結果集應當是想法輸入的就代表著我們的字符串的組成是個和個。我們需要跟蹤和的使用情況，來判斷下一步的操作是否合法。題目詳情 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

figofuture 2019-08-15 14:43 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
構造n個成對括號

摘要：構造個成對括號給出一個整數，實現一個函數生成對小括號，對小括號的左右括弧順序不限，但應該閉合。思路的情況為時的括號串中在縫隙位置再插入一個括號，如中位置。遞歸解決，時為在和中再插入一個括號。構造n個成對括號 Generate Parentheses 給出一個整數n，實現一個函數生成n對小括號，n對小括號的左右括弧順序不限，但應該閉合。 Given n pairs of parent...

姘擱『 2019-07-30 14:20 評論0 收藏0