《剑指offer第二版》面试题38：字符串的排列（java）

题目描述

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

解题思路：

1. 把字符串分为两部分，一部分是字符串的第一个字符，另一部分是字符串除了第一个字符后面的所有字符。
2. 求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。以abc为例子，字符a和后面所有的字符依次交换的结果为：a|b|c|, b|a|c|, c|b|a|
3. 再把后面的字符分为两个部分：后面字符的第一个字符，以及这个字符后面的所有字符。
4. 可通过递归来求解。

代码

void permutation(char[] chars){
    if (chars == null || chars.length <= 0) {
        return;
    }
    rPermutation(chars, 0);
}

/**
 * @param chars 字符串
 * @param index 第一个字符的位置
 */
void rPermutation(char[] chars, int index){
    if (index >= chars.length - 1 ) {
        // 说明已经排列好了，打印出结果
        System.out.println(chars);
        return;
    }
    for (int i = index; i < chars.length; i++) {
        swap(chars, index, i);          // 1. 将第一个字符和后面的字符交换
        rPermutation(chars, index + 1); // 2. 递归排列第二部分字符串
        swap(chars, index, i);          // 3. 把1中交换的字符串还原回来，再进行后续的交换
    }
 }
 void swap(char[] chars, int index1, int index2){
     char tmp = chars[index1];
     chars[index1] = chars[index2];
     chars[index2] = tmp;
 }