本系列導航：劍指offer（第二版）java實現(xiàn)導航帖](http://www.reibang.com/p/010410a4d419)
面試題38：字符串的排列
題目要求：
輸入一個字符串擅腰，打印出該字符串中字符的所有排列内舟。如輸入abc，則打印abc弄匕，acb，bac舶衬，bca暑脆，cab箱亿，cba。
解題思路：
排列與組合是數(shù)學上的常見問題贱呐。解題思路與數(shù)學上求排列總數(shù)類似：首先確定第一個位置的元素丧诺，然后依次確定每一個位置。以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相同，跳過
考慮了字符重復的解法的實現(xiàn)如下
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
