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() 针对任意对象,排序类型为传入的对象类,对于 基本类型数组 其底层是快速排序,对于 对象数组 其底层是归并排序。
  1. 返回值类型为 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;
        }
    }
}