[每日一题]38.字符串的排列
剑指 Offer 38. 字符串的排列 输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
举例：
输入：s = “abc” 输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
Solution
class Solution {
// 存放最终结果
List<String> res = new ArrayList();
// 全局标记数组：两个作用，用于树枝去重 & 树层去重，因为可排序。
// 当然可以选择排序后，全局标记数组（树枝去重） + 本层标记数组（树层去重）
boolean[] flag = new boolean[26];
// 拼接结果
StringBuilder path = new StringBuilder();
int len = 0;
public String[] permutation(String s) {
// 转化为数组，方便排序
char[] c = s.toCharArray();
Arrays.sort(c);
len = c.length;
back(c);
return res.toArray(new String[]{});
}
void back(char[] c){
// 终止条件
if(path.length() == len){
res.add(new String(path));
return;
}
// 横向遍历
for(int i = 0; i < len; i++){
// 树层去重
if(i > 0 && c[i] == c[i - 1] && !flag[i - 1]) continue;
// 树枝去重
if(flag[i]) continue;
// 标记
flag[i] = true;
path.append(c[i]);
// 纵向遍历
back(c);
// 回溯
flag[i] = false;
path.deleteCharAt(path.length() - 1);
}
}
}