TypeScript算法-22. 括号生成

TypeScript算法-22. 括号生成

• 思路
• 代码

思路

深度搜索题，关键是考虑当前位置能放左括号吗，能放右括号吗，而观察括号串的生成过程可以发现能不能放左/右括号只和当前剩余的左右括号数有关。

所以dfs的函数应该有三个参数：

• ln: 剩余的左括号数量
• rn: 剩余的右括号数量
• curStr: 当前拼的字符串

边界条件：当ln = rn = 0的时候就可以把curStr作为一个解记录下来了。

而只要还有左括号，即ln !== 0，就可以放置一个左括号继续深搜，即dfs（ln - 1, rn, curStr + '(')；
什么时候可以放右括号呢？当剩余的右括号比左括号多的时候就可以放置右括号了，然后继续深搜即dfs(ln, rn - 1, curStr + ')')

代码

function generateParenthesis(n: number): string[] {
    const res: string[] = [];

    function dfs(ln: number, rn: number, curStr: string) {
        if (ln === 0 && rn === 0) {
            res.push(curStr);
            return;
        }
        if (ln > 0) {
            // 只要还有左括号，就可以先拼接左括号
            dfs(ln - 1, rn, curStr + '(');
        }
        if (ln < rn) {
            // 剩余的右括号比左括号多就可以拼一个右括号
            dfs(ln, rn - 1, curStr + ')');
        }
    }

    dfs(n, n, '');
    return res;
}

console.log(generateParenthesis(3));