字符串的全排列

剑指offer面试题系列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出 abc,acb,bac,bca,cab,cba。

分析

此题最开始拿到的时候，想了很长时间，终于想到了只有用递归这种方法，才能将所有的字符串打印出来。

递归的思路：

由于Java语言的特点，必须先要将字符串对象用 toCharArray() 这个方法来将其转换成字符数组来进行操作。

需要开辟另外一个数组，来对其进行各种交换操作；因为如果直接在这个数组上进行操作，则在进行交换后，原来的数组已经被改变，下一轮的改变很可能变成和之前变过的数组一样的结果。

一句话，每改变字符数组的第一个元素算是一轮，而每一轮操作的数组必须是原来的数组。

就拿 abc 为例：

第一轮(首字母为 a)：

a b c 
a c b

第二轮操作的对象一定是 abc 这个原来的数组才能保证交换后一定是 b 在第一位，依次类推。

而递归的方式就是：先通过递归，遍历到数组的最右边，然后在退栈的过程中，依次交换，打印。

代码实现

package com.study;

/*字符串的全排列*/
public class suanfa15 {

    public static void StrProc(String str) {
        char[] arr = str.toCharArray();
        FindAllStr(arr, 0, arr.length - 1);
    }

    public static void FindAllStr(char[] arr, int start, int end) {
        if (start >= end)
            return;
        if (start == 0)
            PrintString(arr);// 打印出原来的字符串
        FindAllStr(arr, start + 1, end);//递归遍历到最右边
                        //随着退栈逐步交换
                       // i 作为游标，来递归当前 start 所指位置后面的子序列
        for (int i = start + 1; i <= end; i++) {
            char[] newArr = new char[arr.length];
            SwapToNewArr(arr, newArr, start, i);// 交换不同位置上的数组元素
            PrintString(newArr);
            FindAllStr(newArr, start + 1, end);//递归后面的子序列
        }
    }

    public static void SwapToNewArr(char[] arr, char[] newArr, int i, int j) {
        // 先拷贝原数组
        for (int k = 0; k < arr.length; k++) {
            newArr[k] = arr[k];
        }
        // 再改动交换后的元素
        newArr[j] = arr[i];
        newArr[i] = arr[j];
    }

    public static void PrintString(char[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String str = "abc";
        StrProc(str);
    }
}

备注

全排列不需要考虑重复的问题，比如 acc 这个字符串，两个相同的元素 c c交换也算一次排列， 不用排除。