leetcode 22 Generate Parentheses

figofuture 發布于2019-08-15 14:43 / 2019人閱讀

摘要：要求返回一個中包含組括號所有可能的符合規則的組合。例如輸入結果集應當是想法輸入的就代表著我們的字符串的組成是個和個。我們需要跟蹤和的使用情況，來判斷下一步的操作是否合法。

題目詳情

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.輸入一個正整數n。要求返回一個List,list中包含n組括號所有可能的符合規則的組合。如“（（））”就屬于符合規則的組合，“)(()”就屬于不符合規則的組合。
例如, 輸入 n = 3, 結果集應當是:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

想法

輸入的n就代表著我們的字符串的組成是n個"("和n個")"。

聲明一個cur字符串來暫存我們沒次操作獲得的字符串，而我們每次想要將括號加入cur字符串的時候，我們要保證剩余的括號和現有字符串，可以滿足規則。也就是說，如果我們想加入一個")"，我們要保證cur字符串中的")"的數量小于"("的數量，否則字符串就不符合規則了。

我們需要跟蹤"("和")"的使用情況，來判斷下一步的操作是否合法。

解法

     public List generateParenthesis(int n) {
            List ans = new ArrayList();
            backtrack(ans, "", 0, 0, n);
            return ans;
        }

        public void backtrack(List ans, String cur, int open, int close, int max){
            if (cur.length() == max * 2) {
                ans.add(cur);
                System.out.println(cur);
                return;
            }

            if (open < max)
                backtrack(ans, cur+"(", open+1, close, max);
            if (close < open)
                backtrack(ans, cur+")", open, close+1, max);
        }

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

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

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

LeetCode[22] Generate Parentheses

摘要：復雜度思路注意的地方，要限制左括號和右括號。每出現一次左括號，就相對于限定了，最多只能出現那么多右括號。所以，為了完成這種限定，用來控制。不然會有的情況出現。 LeetCode[22] Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of ...

Jonathan Shieber 2019-08-14 15:02 評論0 收藏0
[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
[Leetcod] Generate Parentheses 產生括號

摘要：而對于右括號，必須前面放了一個左括號，我們才能放一個右括號。所以我們根據剩余可放置左括號，和剩余可放置右括號，代入遞歸，就可以求解。 Generate Parentheses 最新更新請見：https://yanjia.me/zh/2019/01/... Given n pairs of parentheses, write a function to generate all co...

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

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

leo108 2019-08-15 14:26 評論0 收藏0