[Leetcod] Generate Parentheses 產(chǎn)生括號(hào)

Ilikewhite 發(fā)布于2019-08-14 12:45 / 1834人閱讀

摘要：而對于右括號(hào)，必須前面放了一個(gè)左括號(hào)，我們才能放一個(gè)右括號(hào)。所以我們根據(jù)剩余可放置左括號(hào)，和剩余可放置右括號(hào)，代入遞歸，就可以求解。

Generate Parentheses 最新更新請見：https://yanjia.me/zh/2019/01/...

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

回溯法 復(fù)雜度

時(shí)間 O(N) 空間 O(N) 遞歸棧

思路

當(dāng)我們放置一個(gè)新的符號(hào)時(shí)，我們有兩個(gè)選擇，放置左括號(hào)，或者放置右括號(hào)，但是按照題意我們最多放置n個(gè)左括號(hào)，放一個(gè)剩余可放置左括號(hào)就少一個(gè)，但剩余可放置右括號(hào)則多了一個(gè)。而對于右括號(hào)，必須前面放了一個(gè)左括號(hào)，我們才能放一個(gè)右括號(hào)。所以我們根據(jù)剩余可放置左括號(hào)，和剩余可放置右括號(hào)，代入遞歸，就可以求解。

代碼

public class Solution {
    
    List res = new LinkedList();
    
    public List generateParenthesis(int n) {
        helper(n, 0, "");
        return res;
    }
    
    private void helper(int left, int right, String tmp){
        // 如果左括號(hào)右括號(hào)都放完了，則找到一個(gè)結(jié)果
        if(left == 0 && right == 0){
            res.add(tmp);
            return;
        }
        // 對于每個(gè)位置，我們有兩種選擇，要么放左括號(hào)，要么放右括號(hào)
        if (left > 0){
            helper(left - 1, right + 1, tmp+"(");
        }
        if (right > 0){
            helper(left, right - 1, tmp+")");
        }
    }
}

后續(xù) Follow Up

Q:如果想把生成的括號(hào)加上縮進(jìn)來格式化怎么辦？
A:將原先if(left == 00 && right == 0)里面替換為：

int level = 0;
for(int i = 0; i < tmp.length(); i++){
    if(tmp.charAt(i) == "{"){
        for(int k = 0; k < level; k++){
            System.out.print("	");
        }
        System.out.println("{");
        level++;
    } else {
        level--;
        for(int k = 0; k < level; k++){
            System.out.print("	");
        }
        System.out.println("}");
    }
}