这里可以用排序并且比较来剪枝。和题目47. 全排列 II非常类似。
复杂度分析
- 时间复杂度: O ( n ! ) O(n!) O(n!),排序字符串转换成的字符数组需要 O ( n log n ) O(n\log n) O(nlogn),而遍历所有的子串需要 O ( n ! ) O(n!) O(n!)。
- 空间复杂度: O ( n ) O(n) O(n),递归栈的最大深度为字符串的长度,额外使用了长度为 n n n的标记访问数组 v i s i t visit visit和字符数组 c h a r s chars chars
// 很典型的回溯算法,用一个visit数组标记是否访问
// 注意这里的字符串可能有重复的字母,这一点是需要注意的。
class Solution {
boolean[] visit; // 用于标记是否访问
char[] chars;
List<String> list = new LinkedList();
public String[] permutation(String s) {
// 先排好序,用于以后剪枝
this.chars = s.toCharArray();
Arrays.sort(chars);
this.visit = new boolean[chars.length];
bfs(new StringBuffer());
return list.toArray(new String[list.size()]);
}
public void bfs(StringBuffer str){
if(str.length() == chars.length){
list.add(str.toString());
return;
}
for(int i = 0; i < visit.length; i++){
// 剪枝,如果前面一个字符已经访问过,就不再次访问
if(i > 0 && chars[i] == chars[i - 1] && visit[i - 1] == false)
continue;
if(!visit[i]){
str.append(chars[i]);
visit[i] = true;
bfs(str);
str.deleteCharAt(str.length() - 1);
visit[i] = false;
}
}
}
}
不过这题大佬有个更加漂亮的解法,无需排序。如下。依旧是来源Krahets大佬
class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) continue; // 重复,因此剪枝
set.add(c[i]);
swap(i, x); // 交换,将 c[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}