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;
};

参考资料