括号匹配算法是JavaScript中处理字符串括号有效性的常用方法，核心基于栈结构，实现时，初始化空栈遍历字符串：遇左括号（如(、[、{）则入栈，遇右括号则检查栈顶是否匹配对应左括号且栈非空，匹配则出栈，否则直接返回false，遍历结束后，若栈为空则所有括号有效，否则无效，典型应用如校验代码、表单输入格式等，用数组模拟栈，通过push/pop操作高效完成判断，时间复杂度O(n)，空间复杂度O(n)。
JavaScript实现生成括号算法：递归、迭代与动态规划
在算法学习中，"生成有效括号组合"是一个经典问题：给定整数 n，生成所有由 n 对括号组成的、且格式正确的组合，当 n=2 时，输出为 ["(())","()()"]，这个问题不仅考察对括号匹配规则的理解，更涉及递归、迭代、动态规划等多种算法思想，本文将详细介绍如何用 JavaScript 实现生成括号算法，从基础递归到高效动态规划,逐步优化解决方案。
问题理解与核心思路
有效括号的规则
一个括号组合有效,需满足以下两个条件：
- 左括号数量等于右括号数量（
n对）； - 在任意前缀中，左括号数量不少于右括号数量（避免 这样的非法组合）。
核心思路
生成有效括号的本质是"按规则添加括号"：
- 从空字符串开始，每次选择添加 或 ；
- 添加时需确保左括号数量不超过
n,且右括号数量不超过左括号数量； - 当字符串长度达到
2n时,得到一个有效组合。
递归回溯法（最直观）
递归是解决此类"组合生成"问题的天然选择，通过递归枚举所有可能的括号添加路径，并在非法路径时提前终止（剪枝）,即可高效生成有效组合。
算法步骤
- 定义递归函数，参数包括当前字符串
current、左括号数量left、右括号数量right； - 终止条件：当
current.length === 2n时,将当前组合加入结果数组； - 递归过程：
- 若
left < n，可添加 ，递归调用left + 1； - 若
right < left，可添加 ，递归调用right + 1。
- 若
JavaScript 实现
function generateParenthesis(n) {
const result = [];
function backtrack(current, left, right) {
// 终止条件：字符串长度达到 2n
if (current.length === 2 * n) {
result.push(current);
return;
}
// 添加左括号（若左括号未用完）
if (left < n) {
backtrack(current + '(', left + 1, right);
}
// 添加右括号（若右括号少于左括号）
if (right < left) {
backtrack(current + ')', left, right + 1);
}
}
backtrack('', 0, 0);
return result;
}
// 示例：n=2
console.log(generateParenthesis(2));
// 输出：["(())", "()()"]
复杂度分析
- 时间复杂度：
O(4^n / sqrt(n))，第n个卡特兰数（有效括号组合数）约为4^n / (n * sqrt(n))，每个组合需要O(n)时间构建,故总时间复杂度为指数级。 - 空间复杂度：
O(n)（递归调用栈的最大深度为2n，但卡特兰数的影响已包含在时间复杂度中）。
实际应用场景
递归回溯法虽然时间复杂度较高，但在 n 较小（如 n ≤ 8）时实现简单直观，适合教学演示和快速原型开发，在实际面试中,这种方法往往能清晰展示对问题本质的理解。
迭代法（BFS 队列实现）
递归的本质是栈的调用，而迭代可以用队列模拟递归过程，避免递归栈溢出的风险（尽管本题 n 较小时不明显）。
算法步骤
- 初始化队列，存储当前字符串和左右括号数量（如
['', 0, 0]）； - 每次从队列取出一个元素，尝试添加 或 ,若合法则将新状态加入队列；
- 当字符串长度为
2n时,将结果存入数组。
JavaScript 实现
function generateParenthesis(n) {
const result = [];
const queue = [['', 0, 0]]; // [current, left, right]
while (queue.length > 0) {
const [current, left, right] = queue.shift();
if (current.length === 2 * n) {
result.push(current);
continue;
}
if (left < n) {
queue.push([current + '(', left + 1, right]);
}
if (right < left) {
queue.push([current + ')', left, right + 1]);
}
}
return result;
}
// 示例：n=3
console.log(generateParenthesis(3));
// 输出：["((()))","(()())","(())()","()(())","()()()"]
复杂度分析
- 时间复杂度：与递归法相同，
O(4^n / sqrt(n)),需遍历所有合法组合。 - 空间复杂度：
O(4^n / sqrt(n)),队列中最多存储所有中间状态。
优化技巧
在实际应用中，可以使用优先队列或广度优先搜索的变体来优化内存使用，可以限制队列中存储的状态数量,或者使用更高效的数据结构来管理中间状态。
动态规划（高效解法）
动态规划通过"自底向上"构建解，避免重复计算，适合需要多次调用或 n 较大的场景。
算法思路
定义 dp[i] 为 i 对括号的有效组合集合,则：
dp[0] = [""]（空字符串）；dp[i]可由dp[i-1]推导：在i-1对括号的组合中，插入第i对括号，具体有两种方式：- 将 和 包裹在
dp[i-1]的某个组合外（如dp[1] = ["()"]→dp[2] = ["(())"]）； - 将 插入
dp[i-1]的组合开头， 插入中间某个位置（如dp[1] = ["()"]→dp[2] = ["()()"]）。
- 将 和 包裹在
更准确的转移方程：
dp[i] = "(" + x + ")" + y，x 属于 dp[j]，y 属于 dp[i-1-j]，0 ≤ j < i-1。
JavaScript 实现
function generateParenthesis(n) {
const dp = Array.from({ length: n + 1 }, () => []);
dp[0] = ['']; // 初始化：0 对括号只有空字符串
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
const leftParts = dp[j]; // 左边 j 对括号
const rightParts = dp[i - 1 - j]; // 右边 i-1-j 对括号
for (const left of leftParts) {
for (const right of rightParts) {
dp[i].push('(' + left + ')' + right);
}
}
}
}
return dp[n];
}
// 示例：n=3
console.log(generateParenthesis(3));
// 输出：["((()))","(()())","(())()
