牛客题目链接
1. 题目考点
- 回溯剪枝条件
2. 考点解析
除开第一个重复元素外 其余重复元素开始全排必定重复
import java.util.*;
public class Solution {
ArrayList<String> res = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if (str == null || str.equals("")) return res;
char[] strs = str.toCharArray();
// 关键:排序使重复元素相邻
Arrays.sort(strs);
boolean[] used = new boolean[strs.length];
StringBuilder path = new StringBuilder();
backTrace(strs,path,used);
return res;
}
public void backTrace(char[] strs, StringBuilder path, boolean[] used) {
if (path.length() == strs.length) {
res.add(path.toString());
return ;
}
for (int i = 0; i < strs.length; i++) {
if (used[i] == true) continue;
// 关键:剪枝条件 相邻元素相同 且前一个元素未使用
if (i > 0 && strs[i] == strs[i-1] && used[i-1] == false)
continue;
used[i] = true;
path.append(strs[i]);
backTrace(strs, path, used);
used[i] = false;
path.deleteCharAt(path.length() - 1);
}
}
}