LeetCode第二十二题：括号生成

admin
学习
2024-03-14
50热度
0评论

题目来源：https://leetcode.cn/problems/generate-parentheses/description/

1.题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

提示：

1 <= n <= 8

2.解题思路

解法一：回溯法

描述：从一个空字符串开始，左括号和右括号的数量都为0。在每一步，我们有两个选择，要么添加一个左括号（如果左括号的数量小于n），要么添加一个右括号（如果右括号的数量小于左括号的数量）。左括号的添加受到其数量小于n的限制；右括号的添加受到其数量必须小于左括号的数量的限制，以确保字符串的有效性。当字符串长度达到2n时，意味着找到了一个有效的组合，将其添加到结果集中。在探索一个分支（比如添加左括号）之后，回溯以探索另一个分支（添加右括号），以此类推，直到所有可能的组合都被探索完毕。
时间复杂度：O(4^n / (n^(3/2)))。精确计算这个问题的时间复杂度相对复杂，它和卡特兰数（Catalan number）有关
空间复杂度：O(n)。递归栈的最大深度为2n（因为最长的有效字符串长度为2n），所以递归栈空间为O(2n)。
参考代码：

java版：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        // 开始回溯过程，从空字符串开始，初始左右括号都为0
        backtrack(combinations, "", 0, 0, n);
        return combinations;
    }

    private void backtrack(List<String> combinations, String current, int open, int close, int max) {
        // 如果当前字符串长度等于2*n，表示形成了一个完整的组合
        // 将其添加到解集中，然后返回
        if (current.length() == max * 2) {
            combinations.add(current);
            return;
        }
        // 如果左括号数量小于n，可以放置一个左括号
        // 因为左括号可以随时添加，只要不超过n个
        if (open < max) {
            // 在当前字符串基础上添加一个左括号，然后递归调用
            // 同时，左括号数量加一
            //例如
            backtrack(combinations, current + "(", open + 1, close, max);
        }
        // 如果右括号数量小于左括号数量，可以放置一个右括号
        // 右括号添加的前提是不超过左括号的数量，以保证序列的有效性
        if (close < open) {
            // 在当前字符串基础上添加一个右括号，然后递归调用
            // 同时，右括号数量加一
            backtrack(combinations, current + ")", open, close + 1, max);
        }
    }
}

C++版：

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<string> combinations;
		backtrack(combinations, "", 0, 0, n);
		return combinations;
	}

private:
	void backtrack(vector<string>& combinations, string current, int open, int close, int max) {
		// 如果当前字符串长度等于2*n，表示形成了一个完整的组合
		// 将其添加到解集中，然后返回
		if (current.length() == max * 2) {
			combinations.push_back(current);
			return;
		}
		// 如果左括号数量小于n，可以放置一个左括号
		// 因为左括号可以随时添加，只要不超过n个
		if (open < max) {
			// 在当前字符串基础上添加一个左括号，然后递归调用
			// 同时，左括号数量加一
			backtrack(combinations, current + "(", open + 1, close, max);
		}
		// 如果右括号数量小于左括号数量，可以放置一个右括号
		// 右括号添加的前提是不超过左括号的数量，以保证序列的有效性
		if (close < open) {
			// 在当前字符串基础上添加一个右括号，然后递归调用
			// 同时，右括号数量加一
			backtrack(combinations, current + ")", open, close + 1, max);
		}

	}
};

C版：

// 回溯函数的声明，用于生成所有可能的并且有效的括号组合
void backtrack(char*** array, int* size, char* current, int pos, int open, int close, int max);

// 生成所有可能的并且有效的括号组合
char** generateParenthesis(int n, int* returnSize) {
	// 初始化解的数组和当前解的大小
	char** array = (char**)malloc(sizeof(char*) * 10000); // 假设最大可能的组合数为10000
	*returnSize = 0;
	char* current = (char*)malloc(2 * n + 1); // 当前解的字符串，+1是为了NULL终止符
	current[2 * n] = '\0'; // 设置字符串终止符
	backtrack(&array, returnSize, current, 0, 0, 0, n);
	free(current); // 释放当前解的内存
	return array;
}

// 递归回溯函数
void backtrack(char*** array, int* size, char* current, int pos, int open, int close, int max) {
	// 当前字符串已完成，添加到解的数组中
	if (pos == max * 2) {
		// 手动复制字符串到新分配的内存
		(*array)[*size] = (char*)malloc(pos + 1); // +1为了NULL终止符
		memcpy((*array)[*size], current, pos + 1);
		(*size)++;
		return;
	}

	// 如果左括号数量小于max，添加一个左括号并递归
	if (open < max) {
		current[pos] = '(';
		backtrack(array, size, current, pos + 1, open + 1, close, max);
	}

	// 如果右括号数量小于左括号，添加一个右括号并递归
	if (close < open) {
		current[pos] = ')';
		backtrack(array, size, current, pos + 1, open, close + 1, max);
	}
}

解法二：动态规划

描述：定义一个动态规划的表dp，其中dp[i]存储所有由i对括号组成的有效组合。初始化dp[0]为只含有一个空字符串的列表，因为没有括号自然只有一个有效的组合，即不包含任何字符。对于每一个i从1到n，通过以下方式构建dp[i]：遍历j从0到i-1，其中j表示在新括号对内部的括号对数。对于每个j，将dp[j]中的每个字符串s1取出，然后对每个dp[i-j-1]中的字符串s2，构造新的字符串"(" + s1 + ")" + s2，并将其加入到dp[i]中。最后，dp[n]包含了所有由n对括号组成的有效组合，直接返回作为结果。
时间复杂度：O(n2)
空间复杂度：O(n)
参考代码：

java版：

class Solution {
    public List<String> generateParenthesis(int n) {
        // 动态规划列表，dp[i]存储i对括号的所有有效组合
        List<List<String>> dp = new ArrayList<>();
        // 初始化0对括号时的解集，只有一个空字符串
        dp.add(new ArrayList<>());

        dp.get(0).add("");
        // 从1对括号开始，逐步构建到n对括号的解
        // 例如n=3
        for (int i = 1; i <= n; i++) {
            // 当前i对括号的所有有效组合
            List<String> current = new ArrayList<>();
            // 遍历到当前i对括号的所有可能的情况
            for (int j = 0; j < i; j++) {
                // first：在新括号内部的组合
                // second：在新括号外部的组合
                // 对于每一种情况，都尝试在dp[j]的基础上添加新括号组合，并与dp[i-1-j]组合
                // dp[2] 构建过程：
                // j = 0: 在dp[0]的基础上插入"()"，然后加上dp[1]，得到："()()"。
                // j = 1: 在dp[1]的基础上插入"()"，得到："(()"，再加上dp[0]，得到："((()))"。
                // 结果：dp[2] = ["(())", "()()"]。
                // dp[3] 构建过程：
                // j = 0: 在dp[0]的基础上插入"()"，然后加上dp[2]的所有可能性，得到：
                // "()(())"
                // "()()()"
                // j = 1: 在dp[1]即"()"的基础上插入"()"，然后加上dp[1]的所有可能性，得到：
                // "(())()"
                // j = 2: 在dp[2]即["(())",
                // "()()"]的基础上插入"()"，然后加上dp[0]的所有可能性，得到：
                // "((()))"
                // "(()())"
                // 结果：dp[3] = ["((()))", "(()())", "(())()", "()(())", "()()()"]。
                for (String first : dp.get(j)) {
                    for (String second : dp.get(i - 1 - j)) {
                        // 组合生成新的括号组合，并添加到当前i对括号的解集中
                        current.add("(" + first + ")" + second);
                    }
                }
            }
            // 将当前i对括号的所有有效组合添加到dp中
            dp.add(current);
        }
        // 返回n对括号的所有有效组合
        return dp.get(n);
    }
}

C++版：

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<vector<string>> dp(n + 1);

		dp[0].push_back("");
		// 从1对括号开始，逐步构建到n对括号的解
		// 例如n=3
		for (int i = 1; i <= n; i++) {
			// 遍历到当前i对括号的所有可能的情况
			for (int j = 0; j < i; j++) {
				// left：在新括号内部的组合
				// right：在新括号外部的组合
				// 对于每一种情况，都尝试在dp[j]的基础上添加新括号组合，并与dp[i-1-j]组合
				// dp[2] 构建过程：
				// j = 0: 在dp[0]的基础上插入"()"，然后加上dp[1]，得到："()()"。
				// j = 1: 在dp[1]的基础上插入"()"，得到："(()"，再加上dp[0]，得到："((()))"。
				// 结果：dp[2] = ["(())", "()()"]。
				// dp[3] 构建过程：
				// j = 0: 在dp[0]的基础上插入"()"，然后加上dp[2]的所有可能性，得到：
				// "()(())"
				// "()()()"
				// j = 1: 在dp[1]即"()"的基础上插入"()"，然后加上dp[1]的所有可能性，得到：
				// "(())()"
				// j = 2: 在dp[2]即["(())",
				// "()()"]的基础上插入"()"，然后加上dp[0]的所有可能性，得到：
				// "((()))"
				// "(()())"
				// 结果：dp[3] = ["((()))", "(()())", "(())()", "()(())", "()()()"]。
				for (const string& left : dp[j]) {
					for (const string& right : dp[i - j - 1]) {
						dp[i].push_back("(" + left + ")" + right);
					}
				}
			}
		}
		// 返回n对括号的所有有效组合
		return dp[n];
	}
};

C版：

char** generateParenthesis(int n, int* returnSize) {
	// 初始化dp数组，每个元素指向一个字符指针数组
	char*** dp = (char***)malloc((n + 1) * sizeof(char**));
	int* dpSize = (int*)malloc((n + 1) * sizeof(int)); // 每个dp[i]的大小
	for (int i = 0; i <= n; ++i) {
		dp[i] = NULL;
		dpSize[i] = 0;
	}

	// 基础情况
	dp[0] = (char**)malloc(sizeof(char*));
	dp[0][0] = (char*)malloc(1);
	dp[0][0][0] = '\0'; // 空字符串
	dpSize[0] = 1;

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int k = 0; k < dpSize[j]; ++k) {
				for (int l = 0; l < dpSize[i - j - 1]; ++l) {
					// 构造新字符串：左侧部分+新括号+右侧部分
					int leftLen = strlen(dp[j][k]);
					int rightLen = strlen(dp[i - j - 1][l]);
					char* newStr = (char*)malloc(leftLen + rightLen + 3); // 加上新括号和'\0'
					strcpy(newStr, "(");
					strcat(newStr, dp[j][k]);
					strcat(newStr, ")");
					strcat(newStr, dp[i - j - 1][l]);

					// 添加到dp[i]
					dpSize[i]++;
					dp[i] = (char**)realloc(dp[i], dpSize[i] * sizeof(char*));
					dp[i][dpSize[i] - 1] = newStr;
				}
			}
		}
	}

	*returnSize = dpSize[n];
	char** result = (char**)malloc(*returnSize * sizeof(char*));
	for (int i = 0; i < *returnSize; ++i) {
		result[i] = dp[n][i];
	}

	// 释放内存
	for (int i = 0; i < n; ++i) { // 注意n不释放，因为结果还在使用
		for (int j = 0; j < dpSize[i]; ++j) {
			free(dp[i][j]);
		}
		free(dp[i]);
	}
	free(dp);
	free(dpSize);

	return result;
}