本系列导航：剑指offer（第二版）java实现导航帖](http://www.jianshu.com/p/010410a4d419)
面试题38：字符串的排列
题目要求：
输入一个字符串，打印出该字符串中字符的所有排列。如输入abc，则打印abc，acb，bac，bca，cab，cba。
解题思路：
排列与组合是数学上的常见问题。解题思路与数学上求排列总数类似：首先确定第一个位置的元素，然后依次确定每一个位置。以abc为例，我之前更习惯于设置三个空，然后选择abc中的元素放入上述的空中。而书中给的思路是通过交换得到各种可能的排列，具体思路如下：
对于a,b,c（下标为0,1,2）
0与0交换,得a,b,c => 1与1交换,得a,b,c =>2与2交换,得a,b,c(存入)
=> 1与2交换，得a,c,b =>2与2交换,得a,c.b(存入)
0与1交换,得b,a,c => 1与1交换,得b,a,c =>2与2交换,得b,a,c(存入)
=> 1与2交换，得b,c,a =>2与2交换,得b,c,a(存入)
0与2交换,得c,b,a => 1与1交换,得c,b,a =>2与2交换,得c,b,a(存入)
=> 1与2交换，得c,a,b =>2与2交换,得c,a.b(存入)
书中解法并未考虑有字符重复的问题。对于有重复字符的情况如a,a,b,交换0,1号元素前后是没有变化的，即从生成的序列结果上看，是同一种排列，因此对于重复字符，不进行交换即可，思路如下：
对于a,a,b（下标为0,1,2）
0与0交换,得a,a,b => 1与1交换,得a,a,b =>2与2交换,得a,a,b(存入)
=> 1与2交换，得a,b,a =>2与2交换,得a,b,a(存入)
0与1相同,跳过
0与2交换,得b,a,a =>1与1交换,得b,a,a =>2与2交换,得b,a,a(存入)
=>1与2相同，跳过
考虑了字符重复的解法的实现如下
package chapter4;
import java.util.*;
/**
* Created by ryder on 2017/7/22.
* 字符串的排列
*/
public class P197_StringPermutation {
public static List<char[]> permutation(char[] strs) {
if (strs == null || strs.length == 0)
return null;
List<char[]> ret = new LinkedList<>();
permutationCore(strs, ret, 0);
return ret;
}
//下标为bound的字符依次与[bound,length)的字符交换，如果相同不交换，直到最后一个元素为止。
//如a,b,c
//0与0交换,得a,b,c => 1与1交换,得a,b,c =>2与2交换,得a,b,c(存入)
// => 1与2交换，得a,c,b =>2与2交换,得a,c.b(存入)
//0与1交换,得b,a,c => 1与1交换,得b,a,c =>2与2交换,得b,a,c(存入)
// => 1与2交换，得b,c,a =>2与2交换,得b,c,a(存入)
//0与2交换,得c,b,a => 1与1交换,得c,b,a =>2与2交换,得c,b,a(存入)
// => 1与2交换，得c,a,b =>2与2交换,得c,a.b(存入)
//如a,a,b
//0与0交换,得a,a,b => 1与1交换,得a,a,b =>2与2交换,得a,a,b(存入)
// => 1与2交换，得a,b,a =>2与2交换,得a,b,a(存入)
//0与1相同,跳过
//0与2交换,得b,a,a =>2与2交换，得b,a,a(存入)
public static void permutationCore(char[] strs, List<char[]> ret, int bound) {
if (bound == strs.length)
ret.add(Arrays.copyOf(strs, strs.length));
Set<Character> set = new HashSet<>();
for (int i = bound; i < strs.length; i++) {
if (set.add(strs[i])) {
swap(strs, bound, i);
permutationCore(strs, ret, bound + 1);
swap(strs, bound, i);
}
}
}
public static void swap(char[] strs, int x, int y) {
char temp = strs[x];
strs[x] = strs[y];
strs[y] = temp;
}
public static void main(String[] args) {
char[] strs = {'a', 'b', 'c'};
List<char[]> ret = permutation(strs);
for (char[] item : ret) {
for (int i = 0; i < item.length; i++)
System.out.print(item[i]);
System.out.println();
}
System.out.println();
char[] strs2 = {'a', 'a', 'b','b'};
List<char[]> ret2 = permutation(strs2);
for (char[] item : ret2) {
for (int i = 0; i < item.length; i++)
System.out.print(item[i]);
System.out.println();
}
}
}
运行结果
abc
acb
bac
bca
cba
cab
aabb
abab
abba
baab
baba
bbaa
