本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖](http://www.itdecent.cn/p/010410a4d419)

面試題38：字符串的排列

題目要求：
輸入一個(gè)字符串，打印出該字符串中字符的所有排列。如輸入abc，則打印abc，acb，bac，bca，cab，cba。

解題思路：
排列與組合是數(shù)學(xué)上的常見問題。解題思路與數(shù)學(xué)上求排列總數(shù)類似：首先確定第一個(gè)位置的元素，然后依次確定每一個(gè)位置。以abc為例，我之前更習(xí)慣于設(shè)置三個(gè)空，然后選擇abc中的元素放入上述的空中。而書中給的思路是通過交換得到各種可能的排列，具體思路如下：

對于a,b,c（下標(biāo)為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(存入)

書中解法并未考慮有字符重復(fù)的問題。對于有重復(fù)字符的情況如a,a,b,交換0,1號元素前后是沒有變化的，即從生成的序列結(jié)果上看，是同一種排列，因此對于重復(fù)字符，不進(jìn)行交換即可，思路如下：

對于a,a,b（下標(biāo)為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相同，跳過

考慮了字符重復(fù)的解法的實(shí)現(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;
    }
    //下標(biāo)為bound的字符依次與[bound,length)的字符交換，如果相同不交換，直到最后一個(gè)元素為止。
    //如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();
        }
    }
}

運(yùn)行結(jié)果

abc
acb
bac
bca
cba
cab

aabb
abab
abba
baab
baba
bbaa