首页 > 代码库 > LeetCode 21 Generate Parentheses

LeetCode 21 Generate Parentheses

2024-07-20 16:57:59   219人阅读

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

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

思路：假设当前字串已经有r个"("，t个“)”，则
1若r=n,且t<n时，则只能向该字串中添加")";
2.若r=t,且t<n时，，则只能向该字串中添加"（";
3.若r>t,且t<n时，，则有两种方案 向该字串中添加"（"; 复制该字串，向复制的字符串中添加“)”
public class Solution {
	public List<String> generateParenthesis(int n) {
		int i, j, k, counter, len;
		String str;
		ArrayList<String> result = new ArrayList<String>();
		if (n < 1)
			return result;
		result.add(new String("("));

		for (i = 1; i < 2 * n; i++) {
			len = result.size();
			for (j = 0; j < len; j++) {
				counter = 0;
				for (k = 0; k < result.get(j).length(); k++) {
					if (result.get(j).charAt(k) == '(')
						counter++;
				}
				if(2 * counter ==result.get(j).length()&&counter<n){
					str = result.get(j) + '(';
					result.set(j, str);
				}
				if (2 * counter > result.get(j).length() && counter < n) {
					str = result.get(j) + '(';
					result.add(str);
					str = result.get(j) + ')';
					result.set(j, str);
				}
				if(counter==n){
					str = result.get(j) + ')';
					result.set(j, str);
				}
			}
		}
		return result;
	}
}


LeetCode 21 Generate Parentheses


联系
我们