【剑指 Offer_38】字符串的排列_Java_深度优先搜索解法
剑指 Offer_38——字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素
示例:
输入：s = “abc”
输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
限制：
1 <= s 的长度 <= 8
解题方案
排列方案数量： 对于一个长度为 n 的字符串（假设字符互不重复），其排列共有n×(n−1)×(n−2)…×2×1 种方案。这个比较容易发现。
排列方案的生成方法： 根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第 1 位字符（ n 种情况）、再固定第 2 位字符（ n-1种情况）、… 、最后固定第 n 位字符（ 1种情况）。
以abc为例：
重复方案与剪枝： 当字符串存在重复字符时，排列方案中也存在重复方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。
递归解析：
终止条件： 当 x = len（c） - 1 时，代表所有位已固定（最后一位只有 11 种情况），则将当前组合 c 转化为字符串并加入 res，并返回；
递推参数： 当前固定位 xx ；
递推工作： 初始化一个 Set ，用于排除重复的字符；将第 x位字符与 i∈[x,len©] 字符分别交换，并进入下层递归；
剪枝： 若 c[i]在 Set 中，代表其是重复字符，因此“剪枝”；将 c[i] 加入 Set ，以便之后遇到重复字符时剪枝；
固定字符： 将字符 c[i]和 c[x]交换，即固定 c[i]为当前位字符；
开启下层递归： 调用 dfs(x + 1)，即开始固定第 x + 1个字符；
还原交换： 将字符 c[i]和 c[x] 交换（还原之前的交换）；
class Solution {
//为了让递归函数添加结果方便，定义到函数之外，这样无需带到递归函数的参数列表中
List<String> list = new ArrayList<>();
//同；但是其赋值依赖c，定义声明分开
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
//从第一层开始递归
dfs(0);
//将字符串数组ArrayList转化为String类型数组
return list.toArray(new String[list.size()]);
}
private void dfs(int x) {
//当递归函数到达第三层，就返回，因为此时第二第三个位置已经发生了交换
if (x == c.length - 1) {
//将字符数组转换为字符串
list.add(String.valueOf(c));
return;
}
//为了防止同一层递归出现重复元素
HashSet<Character> set = new HashSet<>();
//这里就很巧妙了,第一层可以是a,b,c那么就有三种情况，这里i = x,正巧dfs(0)，正好i = 0开始
// 当第二层只有两种情况，dfs(1）i = 1开始
for (int i = x; i < c.length; i++){
//发生剪枝，当包含这个元素的时候，直接跳过
if (set.contains(c[i])){
continue;
}
set.add(c[i]);
//交换元素，这里很是巧妙，当在第二层dfs(1),x = 1,那么i = 1或者 2， 不是交换1和1，要就是交换1和2
swap(i,x);
//进入下一层递归
dfs(x + 1);
//返回时交换回来，这样保证到达第1层的时候，一直都是abc。这里捋顺一下，开始一直都是abc，那么第一位置总共就3个交换
//分别是a与a交换，这个就相当于 x = 0, i = 0;
// a与b交换 x = 0, i = 1;
// a与c交换 x = 0, i = 2;
//就相当于上图中开始的三条路径
//第一个元素固定后，每个引出两条路径,
// b与b交换 x = 1, i = 1;
// b与c交换 x = 1, i = 2;
//所以，结合上图，在每条路径上标注上i的值，就会非常容易好理解了
swap(i,x);
}
}
private void swap(int i, int x) {
char temp = c[i];
c[i] = c[x];
c[x] = temp;
}
}
复杂度分析
时间复杂度 O(N！)： N 为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 N×(N−1)×(N−2)…×2×1 ，因此复杂度为 O(N!)
空间复杂度 O(N^2)全排列的递归深度为 N ，系统累计使用栈空间大小为 O(N) ；递归中辅助 Set 累计存储的字符数量最多为 N+(N−1)+…+2+1=(N+1)N/2 ，即占用 O(N^2)的额外空间