[27.字符串排列] 回溯法的字符串输出顺序详细＋容易理解方法

27.字符串的排列

思路：

1. 建立 ArrayList<> 集合用于输出答案，判断字符串是否为空，若为空直接返回 lists，若不为空则调用 Process() 处理；

2. Process() 参数分别为：由字符串转为的字符数组、存放结果的 lists、当前索引 i；

3. Process() 采用回溯法，首先判断是否满足退出条件，若索引 i 到达字符数组最后一位，则判断当前字符串是否在结果 lists 中，若不在则添加，若在则退出；若不满足退出条件，则开始循环处理：定义 j=i，当 j<字符数组长度时，利用 swap() 方法交换 i 与 j 位置的字符，同时回溯调用 Process()，此时的参数为：交换字符位置后的字符数组、存放结果的 lists、当前索引 i +1；处理完毕后，再次调用 swap() 将字符换回；

4. swap() 方法参数为：字符数组、索引 i、索引 j。作用就是交换 i、j 位置的字符；

5. 利用这种方法得到的顺序为： // 括号内为 (i,j) ，P(,,i+1)

   1.交换 (0,0)，调用 P(,,1)；          //此时为"abc"
   
   ​    交换 (1,1)，调用 P(,,2)；      //此时为"abc"
   
   ​        满足退出条件，添加 "abc"；
   
   ​    换回 (1,1)；
   
   ​    交换 (1,2)，调用 P(,,2)；       //此时为"acb"
   
   ​        满足退出条件，添加 "acb"；
   
   ​    换回 (1,2)，循环结束；          //此时为"abc"
   
   换回 (0,0)， j=0 循环结束；
   
   2.交换 (0,1)，调用 P(,,1)；           //此时为"bac"
   
   ​    交换 (1,1)，调用 P(,,2)；       //此时为"bac"
   
   ​        满足退出条件，添加 "bac"；
   
   ​    换回 (1,1)；
   
   ​    交换 (1,2)，调用 P(,,2)；        //此时为"bca"
   
   ​        满足退出条件，添加 "bca"；
   
   ​    换回 (1,2)；                             //此时为"bac"
   
   换回 (0,1)， j=1 循环结束；           //此时为"abc"
   
   3.交换 (0,2)，调用 P(,,1)；               //此时为"cba"
   
   ​    交换 (1,1)，调用 P(,,2)；          //此时为"cba"
   
   ​        满足退出条件，添加 "cba"；
   
   ​    换回 (1,1)；
   
   ​    交换 (1,2)，调用 P(,,2)；            //此时为"cab"
   
   ​        满足退出条件，添加 "cab"；
   
   ​    换回 (1,2)；                       //此时为"cba"
   
   换回 (0,2)， j=2 循环结束；                //此时为"abc"

知识点：

1. Collections.sort() 和 Arrays.sort() 的使用：

• Collections.sort() 针对集合 List，排序类型为 List 对应的类型，实质上调用了Arrays.sort()，其底层是归并排序。
• Arrays.sort() 针对任意对象，排序类型为传入的对象类，对于 基本类型数组 其底层是快速排序，对于 对象数组 其底层是归并排序。

2. 返回值类型为 ArrayList<> 时，需要定义为 ArrayList<> 类型；

代码

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> lists = new ArrayList<>();
        if(str.length()==0) return lists;
        PermutationProcess(str.toCharArray(),lists,0);
        Collections.sort(lists);
        return lists;
    }

    private void PermutationProcess(char[] ch , List<String> lists,int i){
        if(i == ch.length-1){
            if(!lists.contains(new String(ch))){
                lists.add(new String(ch));
            }
        }else{
            for(int j=i;j<ch.length;j++){
                swap(ch,i,j);
                PermutationProcess(ch,lists,i+1);
                swap(ch,j,i);
            }
        }
    }
    private void swap(char[] ch,int i ,int j){
        if(i != j){
            char tmp = ch[i];
            ch[i] = ch[j];
            ch[j] = tmp;
        }
    }
}