剑指Offer——题38（字符串的排列）

1.题目

输入一个字符串，打印出该字符串中字符的所有排列。

输入：abc

输出：abc、acb、bac、bca、cab、cba。

2.思路

step1:求所有可能出现在第一个位置的字符，即把第一个字符和后面所有字符进行交换。

step2:每次都把一个数固定在前面，让后面的数递归地进行全排列，这样每个数都固定过以后就能找出所有排列。

注：我们把每个数固定在前面并让后面的进行全排列完毕以后，要恢复原来的状态，也就需要交换回来。

3.代码实现

public class Permutation {
    public static void permutation(String s){
        if(s==null||s.length()==0){
            return ;
        }
        permutation(s.toCharArray(),0);
    }

    private static void permutation(char[] array, int pos) {
        if(pos==array.length-1){
            System.out.println(array);
        }
        for (int i=pos;i<array.length;i++){
            char temp=array[pos];
            array[pos]=array[i];
            array[i]=temp;

            permutation(array,pos+1);

            //将数组恢复成原来的排列
            temp=array[pos];
            array[pos]=array[i];
            array[i]=temp;
        }

    }


   @Test
    public void test(){
        String s="abc";
       permutation(s);
   }

}

4.本题扩展——字符串组合

输入：abc

输出：a b c ac ba bac

如果输入n个字符，则这n个字符能构成长度为1的组合，长度为2的组合，……，长度为n的组合。

在求n个字符的长度为m（1<=m<=n）的组合的时候，我们把这n个字符分成两部分：第一个字符和其余的所有字符。如果组合里包含第一个字符，则下一步在剩余的字符里面选取m-1个字符；如果组合里不包含第一个字符，则下一步在剩余的n-1个字符里选取m个字符。也就是说，我们可以把求n个字符组成长度为m的组合的问题，分解成两个子问题，分别求n-1个字符串中长度为m-1的组合，以及求n-1个字符的长度为m的组合。这两个子问题都可以用递归实现。