LeetCode - 22. 括號生成

語言: CN / TW / HK

小知識,大挑戰!本文正在參與“程序員必備小知識”創作活動。


原題:22. 括號生成

題目大意:給定一個 n,生成 n 對括號的有效排列,例如給定的 n 是 3,則有效的排列是:["((()))","(()())","(())()","()(())","()()()"]

通常這樣的排列組合題目可以使用遞歸和深度優先遍歷來完成,先把遞歸的架子寫出來:

``` java void dfs() { // 遞歸的終止條件,也就是在什麼情況下不在進行遞歸調用

// 處理當前層的邏輯

// 進行下一層的遞歸調用

// 如果需要的話,再恢復遞歸調用錢的狀態

} ```

然後,我們需要兩個變量:

  • 一個列表來保存結果集
  • 一個 StringBuffer 用來拼接每一個可能結果

``` java class Solution { List result = new ArrayList<>(); StringBuffer sb = new StringBuffer(); public List generateParenthesis(int n) { dfs(0, 0, n); return result; }

private void dfs() {
    // 遞歸的終止條件,也就是在什麼情況下不在進行遞歸調用

    // 處理當前層的邏輯

    // 進行下一層的遞歸調用

    // 如果需要的話,再恢復遞歸調用錢的狀態
}

} ```

接下來,處理 dfs 方法中的邏輯就可以了。這裏的關鍵是如何生成有效的括號排列,需要滿足以下條件:

  • 如果已經排列的左括號的數量小於 n,則可以追加左括號,也就是,只要左括號沒用完,任何時候都可以追加
  • 如果已經排列的右括號比做擴好少,就可以追加右括號,也就是成對的一組括號,左括號要比右括號線出現。

滿足以上兩個條件就可以了。

最終代碼:

``` java class Solution { List result = new ArrayList<>(); StringBuffer sb = new StringBuffer(); public List generateParenthesis(int n) { dfs(0, 0, n); return result; }

private void dfs(int l, int r, int n) {
    // 遞歸的終止條件,也就是在什麼情況下不在進行遞歸調用
    // 當結果的長度是括號數量的兩倍時,就結束遞歸
    if (sb.length() == n * 2) {
        result.add(sb.toString());
        return;
    }

    // 追加半括號時,滿足上述的任意條件,都可以追加對應的半括號
    // 完成遞歸調用之後,要把之前追加的半括號刪除

    if (l < n) {
        // 處理當前層的邏輯
        sb.append('(');
        // 進行下一層的遞歸調用
        dfs(l + 1, r, n);
        // 如果需要的話,再恢復遞歸調用錢的狀態
        sb.deleteCharAt(sb.length() - 1);
    }
    if (r < l) {
        // 處理當前層的邏輯
        sb.append(')');
        // 進行下一層的遞歸調用
        dfs(l, r + 1, n);
        // 如果需要的話,再恢復遞歸調用錢的狀態
        sb.deleteCharAt(sb.length() - 1);
    }
}

} ```