剑指 Offer 38. 字符串的排列
本问题对应的 leetcode 原文链接：剑指 Offer 38. 字符串的排列
对应配套打卡：【回溯专题】剑指 Offer 38. 字符串的排列
问题描述
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
List<Character> path;
List<String> res;
boolean[] visited;
public String[] permutation(String s) {
this.path = new ArrayList<>();
this.res = new ArrayList<>();
this.visited = new boolean[s.length()];
char[] arr = s.toCharArray();
Arrays.sort(arr);
dfs(arr, 0);
String[] ss = new String[res.size()];
for(int i = 0; i < res.size(); i++){
ss[i] = res.get(i);
}
return ss;
}
// 时间复杂度：O(n*n!) 空间：N,N,递归调用最大深度也是 N，3n,O(n)
void dfs(char[] arr, int k){
if(arr.length == k){
res.add(listToString(path));
return;
}
//进行N叉树搜索
for(int i = 0; i < arr.length; i++){
// 剪枝 aab
if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
continue;
}
if(visited[i] == false){
// 递归访问
visited[i] = true;
path.add(arr[i]);
dfs(arr, k + 1);
path.remove(path.size() - 1);
visited[i] = false;
}
}
}
String listToString(List<Character> list){
StringBuilder b = new StringBuilder();
for(int i = 0; i < list.size(); i++){
b.append(list.get(i));
}
return b.toString();
}
}
时间复杂度：O(n!n)
空间复杂度：O(n^2)