剑指offer：字符串的排序
题意描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路
一、使用DFS算法
从首位开始，每一个位置都从1,2,3分别取值，只当前位优先取当前剩余的元素的最小值，就能保证生成的字符串仅挨与上一次。为了记录每一轮中以取的值，添加一个访问数组，该数组记录哪些元素已被访问，其索引对应排序后的字符串索引。简单过程如下：
- 第一个位置从1,2,3开始遍历，取1后，第二位置也从1,2,3遍历，但发现1已被取过，又为了保证最小，所以取2，第三个位置也从1,2,3遍历，发现1,2都访问过了，取3，这时组成1,2,3
- 第三个位置已经没有元素可以遍历，故回溯到上一层中，第二个位置取3，第三个位置发现1已被访问，2没被访问，故取3, 这时组成1,3,2.
- 第二位置已经没有元素可以遍历了，故回溯到第一个位置了，之后的过程类似。
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if(str == null || str.equals("")) { //输入校验
return result;
}
char[] chars = str.toCharArray(); //字符串转字符数组
Arrays.sort(chars); //排序，保证每次都都是当前剩余元素的最小值
Set<String> set = new LinkedHashSet<>(); //使用set去重
boolean[] vis = new boolean[chars.length]; //标记当前字符是否已经使用过
char[] temp = new char[chars.length];
permutation(0, temp, chars, set, vis);
result.addAll(set); //set中全部元素添加入list
return result;
}
public void permutation(int index, char[] temp, char[] chars,
Set<String> set, boolean[] vis) {
if(index == chars.length) { //说明已经排列全部字符，组成一个结果
set.add(new String(temp));
return;
}
for(int i = 0; i < chars.length; i++) {
if(!vis[i]) { //当前字符没有使用
temp[index] = chars[i]; //加入临时数组
vis[i] = true; //当前字符标记为true
permutation(index + 1, temp, chars, set, vis); //排列下一个字符
vis[i] = false; //回溯记得改变标记位
}
}
}二、分解子问题
可以把排列问题分成固定第一个位置，剩余元素全排列问题。之后对剩余元素又进行同样的处理，固定第一个位置，剩余元素全排列。
1，2，3的全排列问题，可以看做1与23的全排列，2与13的全排列，3与21的全排列的总和。也就是我们可以把原始排列问题划分为2部分，第一部分固定，第二部分为剩余元素全排列。所以只要让第一部分不断与后面的交换元素，然后继续处理当前新组成第二部分的全排列问题即可。而我们求剩余元素的全排列的时候，又可以按下面划分为2部分继续搞，直到剩余的元素个数为1，那么当前组成一个排列。这时向上回溯即可，开始更新各个子问题的第一部分的元素，继续处理新的排列问题。
- 第一轮循环，交换
index=0与i=0的位置（数组没有改变），将1，2，3分成两部分，1与23，对23全排列。 - 第二轮循环，交换
index=0与i=1的位置（1，2交换位置），将1，2，3分成两部分，2与13，对13全排列。 - 第三轮循环，交换
index=0与i=2的位置（1，3交换位置），将1，2，3分成两部分，3与12，对12全排列。
public static ArrayList<String> Permutation2(String str) {
ArrayList<String> result = new ArrayList<>();
if(str == null || str.equals("")) {
return result;
}
char[] chars = str.toCharArray();
Set<String> set = new TreeSet<>(); //使用TreeSet保证字典序
permutation2(0, chars, set);
result.addAll(set);
return result;
}
public static void permutation2(int index, char[] chars, Set<String> set) {
if(index == chars.length - 1) { //此时chars已经是一个结果
set.add(new String(chars));
return;
}
for(int i = index; i < chars.length; i++) {
swap(chars, index, i);
permutation2(index + 1, chars, set);
swap(chars, index, i);
}
}
//交换
public static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}三、思路二优化
优化思路二，不产生重复的排列。
比如对abb进行全排列，使用方法二。
①将字符分为a，bb两部分，会出现abb，bba两种结果。
②将字符分为b，ba两部分，会出现bba，bab两种结果。
可以发现出现了重复排列。
所以对于每一个位置遍历，我们添加一个set用于记录以在该位置出现过的元素。 这样就可以不同set了，但是由于没有字典序的保证，最后对结果集还是要做一次排序。
public static ArrayList<String> Permutation3(String str) {
ArrayList<String> result = new ArrayList<>();
if(str != null && str.length() > 0) {
permutation3(0, str.toCharArray(), result);
Collections.sort(result); //最后对集合进行排序。
}
return result;
}
public static void permutation3(int index, char[] chars, ArrayList<String> result) {
if(index == chars.length - 1) {
result.add(new String(chars));
return;
}
//记录该位置已出现过的元素
Set<Character> characters = new HashSet<>();
for(int i = index; i < chars.length; i++) {
//字符出现在当前位置以外的地方，则不进行交换
if(!(i != index && characters.contains(chars[i]))) {
characters.add(chars[i]); //记录当前字符已经使用
swap(chars, index, i);
permutation3(index + 1, chars, result);
swap(chars, index, i);
}
}
}
public static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}四、字典序算法
字典序基于逆序思想。逆序就是序列中存在较大值在较小值的前面，逆序数就是一个序列中这样的组合有几对。
对于一个排列12345，我们知道当逆序产生的位置越高，该排列的位置越靠后，对应的字典序也就越大。比如12534，逆序产生的位置在第三个位置；51234，逆序的位置产生在最高位第一个位置，故比12534大。结论: 逆序位置越高和逆序对越多，该排列位置越靠后，54321即为最大。
- 当前数列从后往前找到第一个正序对，也就是
P(i) < P(i+1)的位置，并记录该位置i。 - 从后往前找第一个大于i的元素，并记录该位置A。
- 交换两个位置（i，A）的元素
- 对【i+1, length-1】的所有元素变为正序排列。
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if(str == null || str.length() == 0) return list; //输入判断
char[] chars = str.toCharArray();
Arrays.sort(chars);
list.add(new String(chars)); //最小子序列
while(true){
int first = chars.length - 2;
//从右向左寻找，第一个chars[first] 《 chars[first+1] 的位置
while(first >= 0 && chars[first] >= chars[first+1]){
first --;
}
if(first == -1) break; //标志位，退出循环
int index = chars.length - 1;
//从右向左寻找，第一个chars[first] 《 chars[index] 的位置
while(chars[first] >= chars[index]){
index --;
}
swap(chars,first,index); //交换两值
reserver(chars,first+1,chars.length-1); //first+1 后续元素正序排列
list.add(new String(chars));
}
return list;
}
public void swap(char[] chars,int i ,int j){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
public void reserver(char[] chars,int start,int end){
for(int i=start,j=end;i<j;i++,j--){
swap(chars,i,j);
}
}