LeetCode[22] Generate Parentheses

Jonathan Shieber 發(fā)布于2019-08-14 15:02 / 3471人閱讀

摘要：復(fù)雜度思路注意的地方，要限制左括號(hào)和右括號(hào)。每出現(xiàn)一次左括號(hào)，就相對(duì)于限定了，最多只能出現(xiàn)那么多右括號(hào)。所以，為了完成這種限定，用來(lái)控制。不然會(huì)有的情況出現(xiàn)。

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

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

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

代碼

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) {
        // 限制在當(dāng)前這么多左括號(hào)的情況下，最多只能出現(xiàn)那么多的右括號(hào)。
        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云服務(wù)器云服務(wù)器 Parentheses Generate LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65249.html

相關(guān)文章

[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 評(píng)論0 收藏0
leetcode22. Generate Parentheses

摘要：當(dāng)右括號(hào)和左括號(hào)的剩余量均為時(shí)，及為一個(gè)最終結(jié)果。而則會(huì)在直接原來(lái)的對(duì)象上進(jìn)行修改，其指針仍然指向原來(lái)的對(duì)象。因此在遞歸的過(guò)程中使用一定要注意，對(duì)對(duì)象的修改不要相互干擾。題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

騫諱護(hù) 2019-08-14 18:35 評(píng)論0 收藏0
leetcode 22 Generate Parentheses

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

figofuture 2019-08-15 14:43 評(píng)論0 收藏0
leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評(píng)論0 收藏0
構(gòu)造n個(gè)成對(duì)括號(hào)

摘要：構(gòu)造個(gè)成對(duì)括號(hào)給出一個(gè)整數(shù)，實(shí)現(xiàn)一個(gè)函數(shù)生成對(duì)小括號(hào)，對(duì)小括號(hào)的左右括弧順序不限，但應(yīng)該閉合。思路的情況為時(shí)的括號(hào)串中在縫隙位置再插入一個(gè)括號(hào)，如中位置。遞歸解決，時(shí)為在和中再插入一個(gè)括號(hào)。構(gòu)造n個(gè)成對(duì)括號(hào) Generate Parentheses 給出一個(gè)整數(shù)n，實(shí)現(xiàn)一個(gè)函數(shù)生成n對(duì)小括號(hào)，n對(duì)小括號(hào)的左右括弧順序不限，但應(yīng)該閉合。 Given n pairs of parent...

姘擱『 2019-07-30 14:20 評(píng)論0 收藏0