BM58 字符串的排列
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：
要求：空间复杂度 ，时间复杂度
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。
输入：
"ab"返回值：
["ab","ba"]说明：
返回["ba","ab"]也是正确的输入：
"aab"返回值：
["aab","aba","baa"]输入：
"abc"返回值：
["abc","acb","bac","bca","cab","cba"]思路：
都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复项数字的全排列类似，只是这道题输出顺序没有要求。但是为了便于去掉重复情况，我们还是应该参照数组全排列，优先按照字典序排序，因为排序后重复的字符就会相邻，后续递归找起来也很方便。
使用临时变量去组装一个排列的情况：每当我们选取一个字符以后，就确定了其位置，相当于对字符串中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。
- 终止条件： 临时字符串中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
- 返回值： 每一层给上一层返回的就是本层级在临时字符串中添加的元素，递归到末尾的时候就能添加全部元素。
- 本级任务： 每一级都需要选择一个元素加入到临时字符串末尾（遍历原字符串选择）。
递归过程也需要回溯，比如说对于字符串“abbc”，如果事先在临时字符串中加入了a，后续子问题只能是"bbc"的全排列接在a后面，对于b开头的分支达不到，因此也需要回溯：将临时字符串刚刚加入的字符去掉，同时vis修改为没有加入，这样才能正常进入别的分支。
具体做法：
- step 1：先对字符串按照字典序排序，获取第一个排列情况。
- step 2：准备一个空串暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的字符被加入了。
- step 3：每次递归从头遍历字符串，获取字符加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用，也不需要将其纳入。
- step 4：进入下一层递归前将vis数组当前位置标记为使用过。
- step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入字符串的元素，
- step 6：临时字符串长度到达原串长度就是一种排列情况。
图示：
import java.util.*;
public class Solution {
public void recursion(ArrayList<String> res, char[] str, StringBuffer temp,
boolean[] vis) {
//临时字符串满了加入输出
if (temp.length() == str.length) {
res.add(new String(temp));
return;
}
//遍历所有元素选取一个加入
for (int i = 0; i < str.length; i++) {
//如果该元素已经被加入了则不需要再加入了
if (vis[i])
continue;
if (i > 0 && str[i - 1] == str[i] && !vis[i - 1])
//当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
continue;
//标记为使用过
vis[i] = true;
//加入临时字符串
temp.append(str[i]);
recursion(res, str, temp, vis);
//回溯
vis[i] = false;
temp.deleteCharAt(temp.length() - 1);
}
}
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if (str == null || str.length() == 0)
return res;
//转字符数组
char[] charStr = str.toCharArray();
// 按字典序排序
Arrays.sort(charStr);
boolean[] vis = new boolean[str.length()];
//标记每个位置的字符是否被使用过
Arrays.fill(vis, false);
StringBuffer temp = new StringBuffer();
//递归获取
recursion(res, charStr, temp, vis);
return res;
}
}主要思路：循环递归、复制初值以回溯、利用set消重(最开始用set接收，后面遍历取出来的时候虽然结果全都有，但是hashset的顺序不一样，所以这里仅用set作判断，可放入则加入结果列表，不可放入则是重复，丢掉)
import java.util.*;
//用模拟取出换实现 递归 回溯 消重 *千万要搞清楚复制和引用的区别，回溯的断点这里用引用又卡了两小时，吐血
public class Solution {
static HashSet Fin1 = new HashSet();
static ArrayList Fin = new ArrayList();
public ArrayList Permutation(String str) {
//把字符串转化为ArryList able
char[] x = str.toCharArray();
ArrayList able = new ArrayList();
for (int i = 0; i <= x.length - 1 ; i++) {
able.add(x[i]);
}
//开一个空的起始StringBuffer
StringBuffer start = new StringBuffer();
//前者表示当前字符串，后者表示剩余可用字符集
fun(start, able);
return Fin;
}
public void fun(StringBuffer result, ArrayList able) {
//接收当前字符串 开res副本接收result、able1接收able，且以便回溯
StringBuffer res = new StringBuffer(result);
ArrayList able1 = new ArrayList(able);
//
if (able.size() == 0) {
//尝试把结果字符串放入set结果集
if (Fin1.add(res.toString())) {
Fin.add(res.toString());
};
}
if (able.size() != 0) {
//从可用字符集中取一个加到当前字符串
for (int i = 0; i <= able.size() - 1 ; i++) {
res.append(able.get(i));
able1.remove(i);
fun(res, able1);
//这里要回溯，恢复到刚传入的result和able值
able1 = new ArrayList(able);
res = new StringBuffer(result);
}
}
}
}