leetcode22. Generate Parentheses

騫諱護發布于2019-08-14 18:35 / 815人閱讀

摘要：當右括號和左括號的剩余量均為時，及為一個最終結果。而則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。

題目要求

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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

即生成成對的括號，其中括號的數量為n

思路和代碼

這題還是一道典型的在前一種情況的前提下生成當前的情況(backtracking)。這樣的題目往往需要通過遞歸的方式來間接記錄當前的情況。
類似的題目還包括

combination sum 和 combination sum II

Permutations 和 Permutations II

我們只需要確保即將生成的結果中右括號的數量不會超過左括號即可。當右括號和左括號的剩余量均為0時，及為一個最終結果。如果左右括號的剩余量還未達到0，則將繼續添加左括號或是右括號直到左右括號剩余量為0。
代碼如下：

    public List generateParenthesis(int n) {
        List result = new ArrayList();
        if(n<=0){
            return result;
        }
        generateParenthesis(result, "(", n-1, n);
        return result;
        
    }
    
    private void generateParenthesis(List result, String current, int leftRemainCount, int rightRemainCount){
        if(leftRemainCount==0){
            while(rightRemainCount-->0){
                current += ")";
            }
            result.add(current);
            return;
        }
        generateParenthesis(result, current+"(", leftRemainCount-1, rightRemainCount);
        if(rightRemainCount>leftRemainCount){
            generateParenthesis(result, current+")", leftRemainCount, rightRemainCount-1);
        }
    }

利用StringBuilder簡單優化

String和StringBuilder的最大區別在于，對String的任何修改都會生成一個新的String對象，并將當前的String指針指向該新生成的對象。在字符串修改頻繁的場景下可能會帶來大量的內存浪費。而StringBuilder則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用StringBuilder一定要注意，對StringBuilder對象的修改不要相互干擾。
代碼如下：

    public List generateParenthesis2(int n) {
        List rst = new ArrayList<>();
        if(n == 0) {
          return rst;     
        }
        backtracking(rst, new StringBuilder(), n, n);
        return rst;
    }
    private void backtracking(List rst, StringBuilder sb, int left, int right) {
        if(left > right) {
          return;    
        }
        if(left > 0) {
          sb.append("(");
          backtracking(rst, sb, left - 1, right);
          sb.setLength(sb.length() - 1);
        }
        if(right > 0) {
          sb.append(")");
          backtracking(rst, sb, left, right - 1);
          sb.setLength(sb.length() - 1);
        }
        
        if(left == 0 && right == 0) {
          rst.add(sb.toString());  
        }
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

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

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