LeetCode Question 22: Generation-parentheses

Knowledge Point Forecast

1. Application of depth-first traversal;
2. Recursive understanding;
3. Transfer of result set: parameter transfer, class member variable transfer;

Topic Requirements

Example

My thoughts

Firstly, the remaining number of known conditions (remember'('the remaining number is left,') is right)':

1. The first character must be'(');
2. In the process of construction, right must be greater than or equal to left, otherwise mismatch will occur.
3. When right > left, you can fill in'(', you can also fill in')', but when right=left, you can only fill in'(');

public List<String> generateParenthesis(int n) {
	List<String> result=new ArrayList<>();
	result.add("(");
	return generateStep(n-1,n,result);
}
private List<String> generateStep(int leftNum,int rightNum,List<String> originResult){
	int originLength=originResult.size();
	if(leftNum==0){//In only one case, output the right parentheses
		StringBuilder builder=new StringBuilder(rightNum);
		for(int i=0;i<rightNum;i++){
			builder.append(')');
		}
		String lastString=builder.toString();
		for(int i=0;i<originLength;i++){
			originResult.set(i,originResult.get(i)+lastString);
		}
		return originResult;
	}else{//It can be divided into two cases, one is to output a left parenthesis, the other is to output a right parenthesis.
		if(rightNum>leftNum) {//You can either output right parentheses or left parentheses
			List<String> newBranch = copy(originResult);
			for (int i = 0; i < originLength; i++) {
				newBranch.set(i, newBranch.get(i) + ")");//Output right parentheses
				originResult.set(i,originResult.get(i)+"(");//Output left parentheses
			}
			newBranch=generateStep(leftNum,rightNum-1,newBranch);
			originResult=generateStep(leftNum-1,rightNum,originResult);
			originResult.addAll(newBranch);
			return originResult;
		}else if(rightNum==leftNum){//Only left parentheses can be output
			for(int i=0;i<originLength;i++){
				originResult.set(i,originResult.get(i)+"(");
			}
			return generateStep(leftNum-1,rightNum,originResult);
		}else{
			//It's never here, as long as the initial value of the call ok
			return originResult;
		}
	}
}
public static List<String> copy(List<String> src){
	List<String> newList=new ArrayList<>(src.size());
	newList.addAll(src);
	return newList;
}

Excellent Solution

//Solution A
public List<String> generateParenthesis(int n) {
	List<String> rst = new ArrayList<>();
	dfs(n, n, "", rst);
	return rst;
}
public void dfs(int left, int right, String s, List<String> rst) {
	if(0 == left&& 0 == right) {
		rst.add(new String(s));
		return;
	}
	if(left>0)
		dfs(left -1, right, s + "(", rst);
	if(right>left&&left>=0)
		dfs(left, right -1, s + ")", rst);
}

Difference analysis

The solution of this problem is recursive processing, and the conditions for the end of recursion are stipulated by each method in the variables.

However, in terms of recursive implementation, the excellent solution is more standardized, at first glance, the regular army; and the solution of its own is more "earth". Why do we say "earth"?

1. In my solution, I make more use of the habit of "human brain". This problem lies in LeetCode Question 17 Solutions are also exposed; after analyzing the process of human brain problem solving, I programmed it.
2. In my solution, my code takes over the expansion process of list, and does more than one thing.

The reason for the same shortcomings in No. 17 is that when I brushed the questions, I did not summarize and think about them, so the methods of solving the problems naturally showed the same characteristics.

Summary of Knowledge Points

1. Application of depth-first traversal;
2. Recursive understanding;
3. Transfer of result set: parameter transfer, class member variable transfer;