22. Generate Parentheses

Leetcode 問題: 22. Generate Parentheses
Categories:
Tags:

題目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

傳入一個整數 n，產生出數量為 n 對 的括號組合陣列

Example

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1
Output: ["()"]

演算法

1. 設定括弧 Stack 儲存資料

因為括弧是按照順序才能夠成為一個合法的括弧，所以用 Stack 的 push 及 pop 控制括弧資料為 先進後出 FILO 的方式

  • 開啟的括弧，必須有一個結束的同類型括弧
  • 開啟的括弧，必須用正確的順序結束括弧關閉

2. 當 起始括弧 ( 數量小於目標括弧對數，繼續加入起始括弧

當起始括弧 (數量未達指定上限數量時，表示都還可以加入起始括弧 (

那就將起始括弧 (加入到 Stack 中

然後將起始括弧數量 +1，遞迴呼叫括弧產生函數

產生結束後，Stack.pop() 移除剛剛加入的起始括弧 (

3. 當 結束括弧 ) 數量小於起始括弧 (數量，加入結束括弧

結束括弧 ) 數量不可以比 起始括弧 ( 數量還多，這樣會變成不合法的括弧字串

當要加入 結束括弧 ) 前，在前方必須有足夠數量的 起始括弧 ( 才能夠加入

  • ()) : 不合法

所以當「結束括弧數量」小於「起始括弧數量」，表示可以加入結束括弧

然後將結束括弧數量 +1，遞迴呼叫括弧產生函數

產生結束後，Stack.pop() 移除剛剛加入的 結束括弧 )

4. 產生合法的括弧

當 起始括弧 ( 、 結束括弧 ) 與 目標括弧對數 這三者的數量相同

表示已經將括弧順序排列組合都排列出來了，將括弧 Stack 中的括弧字串 join 起來，儲存到候選的括弧陣列

答案

JavaScript

function generateParenthesis(nPairParenthesis) {
    // 括號 Stack
    var parenthesisStack = [];
    // 最後的可能括號
    var finalPairParenthesisList = [];
    var backTrack = function (openParenthesisCount, closeParenthesisCount) {
        if (openParenthesisCount == nPairParenthesis && closeParenthesisCount == nPairParenthesis) {
            // 如果已經到最後的數量了
            // 將所有的括號 Stack join 起來
            var finalPairParenthesis = parenthesisStack.join('');
            finalPairParenthesisList.push(finalPairParenthesis);
            return;
        }
        if (openParenthesisCount < nPairParenthesis) {
            // 如果「起始括號數量」小於「目標括號成對數量」
            // 加入起始括號
            parenthesisStack.push("(");
            // 取得下一個括號資料
            backTrack(openParenthesisCount + 1, closeParenthesisCount);
            // 處理結束，將 Stack 中的括弧移除
            parenthesisStack.pop();
        }
        if (closeParenthesisCount < openParenthesisCount) {
            // 如果「結束括弧數量」小於「起始括弧數量」，表示可以加入結束括弧
            parenthesisStack.push(")");
            // 取得下一個括號資料
            backTrack(openParenthesisCount, closeParenthesisCount + 1);
            // 處理結束，將 Stack 中的括弧移除
            parenthesisStack.pop();
        }
    };
    // 從頭開始計算括弧
    backTrack(0, 0);
    return finalPairParenthesisList;
}

TypeScript

function generateParenthesis(nPairParenthesis: number): string[] {
    // 括號 Stack
    let parenthesisStack: any = [];
    // 最後的可能括號
    let finalPairParenthesisList:string[] = [];

    let backTrack = (openParenthesisCount: number, closeParenthesisCount: number):void => {
        if (openParenthesisCount == nPairParenthesis && closeParenthesisCount == nPairParenthesis) {
            // 如果已經到最後的數量了
            // 將所有的括號 Stack join 起來
            let finalPairParenthesis = parenthesisStack.join('');
            finalPairParenthesisList.push(finalPairParenthesis);
            return;
        }

        if (openParenthesisCount < nPairParenthesis) {
            // 如果「起始括號數量」小於「目標括號成對數量」
            // 加入起始括號
            parenthesisStack.push("(");
            // 取得下一個括號資料
            backTrack(openParenthesisCount + 1, closeParenthesisCount);
            // 處理結束，將 Stack 中的括弧移除
            parenthesisStack.pop();
        }

        if (closeParenthesisCount < openParenthesisCount) {
            // 如果「結束括弧數量」小於「起始括弧數量」，表示可以加入結束括弧
            parenthesisStack.push(")");
            // 取得下一個括號資料
            backTrack(openParenthesisCount, closeParenthesisCount + 1);
            // 處理結束，將 Stack 中的括弧移除
            parenthesisStack.pop();
        }
    }

    // 從頭開始計算括弧
    backTrack(0,0);

    return finalPairParenthesisList;
};

參考資料