题意整理

  • 返回输入字符串的所有排列。
  • 将所有排列按字典序排好。

方法一(回溯+set去重)

1.解题思路

  • 基本思路:将字符串转化为字符数组,然后进行递归。递归的过程中,首先固定某一个下标对应元素,然后将其他元素进行交换,并且每次交换后都进行回溯。当游标走到末尾的时候,将对应的数组转化为字符串,加入到结果list。
  • 去重:由于交换的过程中,可能会有重复,所以交换前先构建一个set,当某个字符已经在set,说明交换过了,直接跳过。

动图展示:
图片说明

2.代码实现

import java.util.*;

public class Solution {
    //初始化结果list
    ArrayList<String> res=new ArrayList<String>();

    public ArrayList<String> Permutation(String str) {
        char[] arr=str.toCharArray();
        backtrack(arr,0);
        //字典序排列
        Collections.sort(res);
        return res;
    }

    private void backtrack(char[] arr,int i){
        if(i==arr.length-1){
            //交换到最后一个下标,添加到res
            res.add(String.valueOf(arr));
            return;
        }
        Set<Character> set=new HashSet<>();
        for(int j=i;j<arr.length;j++){
            //如果已经交换过,则直接跳过
            if(!set.contains(arr[j])){
                set.add(arr[j]);
                //交换,递归,回溯
                swap(arr,j,i);
                backtrack(arr,i+1);
                swap(arr,j,i);
            }
        }
    }

    //交换位置
    private void swap(char[] arr,int i,int j){
        char temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

3.复杂度分析

  • 时间复杂度:由于字符串全排列的总数为图片说明 ,并且递归中嵌套着一个循环,所以时间复杂度为图片说明
  • 空间复杂度:辅助set中累计存放的元素为图片说明 ,所以空间复杂度为图片说明

方法二(回溯+标记数组去重)

1.解题思路

  • 基本思路:同样将字符串转化为字符数组,然后进行递归。与方法一不同的是,使用标记数组来判断某位字符是否加入路径。递归的过程依然是从左到右固定每一个字符,同时不断回溯。这种思路与第一种相比更好理解,并且由于递归之前,为了配合后面去重,对arr数组进行了排序,省去了最后的字典序排序操作。

  • 举例说明:对于"ABC"这个字符串,我们第一步可以选择'A'、'B'或'C'添加到sb,如果选择了'A',一种情况是接着选择'B'和'C'添加到可变字符串sb,当sb满3个字符后,就转化为String,加入到res。此时进行回溯,"ABC"退回到"AB"的情况,由于'C'已经选择过了,所以继续退回到'A'的情况,此时'B'已经选择过,'C'经过一轮回溯,重置为未选择状态,所以这一次可以选择'C',接着选择'B'。第一步选择'B'和'C'的情况与上面的过程类似。

  • 去重:有两种情况可以对递归进行剪枝,一种是某个下标对应字符已经被访问过了;另一种情况是相邻下标是相同元素,我们可以在前一个下标为false(即未被访问)的时候,直接剪掉。

2.代码实现

import java.util.*;

class Solution {
    ArrayList<String> res;
    boolean[] v;

    public ArrayList<String> Permutation(String str) {
        //初始化结果集res和标记数组v
        res=new ArrayList<String>();
        v=new boolean[str.length()];
        char[] arr=str.toCharArray();
        Arrays.sort(arr);

        //执行回溯方法
        backtrack(arr,new StringBuilder());
        return res;
    }

    public void backtrack(char[] arr, StringBuilder sb) {
        //递归到最后一层,将其转换为String添加到res
        if (sb.length()==arr.length){
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            //如果某个下标已经访问过,或者前一个相邻下标重复,直接跳过
            if (v[i]||(i>0&&!v[i-1]&&arr[i-1]==arr[i])) {
                continue;
            }
            //修改标记,添加字符,递归,回溯
            v[i]=true;
            sb.append(arr[i]);
            backtrack(arr,sb);
            sb.deleteCharAt(sb.length()-1);
            v[i]=false;
        }
    }
}

3.复杂度分析

  • 时间复杂度:由于字符串全排列的总数为图片说明 ,并且递归中嵌套着一个循环,所以时间复杂度为图片说明
  • 空间复杂度:递归栈的深度最大为n,并且需要额外大小为n的标记数组,所以空间复杂度为图片说明

方法三(下一个排列)

1.解题思路

  • 基本思路:当已知字符串的一个排列时,我们可以在图片说明的时间复杂度内,找到它字典序的下一个排列,由于总共有图片说明种排列,所以总的时间复杂度是图片说明,与前两种方案相比,节省了部分时间,并且没有递归栈的空间开销,只需额外常数级别的内存空间。

  • 如何得到下一个排列:

    1.从后往前,找到第一个递增的索引(记为i),如果找不到,说明没有下一个排列
    2.从后往前,找到第一个大于arr[i]的元素所在下标(记为j)
    3.交换i和j对应下标的元素,并从i+1下标处开始,反转arr,即可得到arr的下一个排列

2.代码实现

import java.util.*;

class Solution {
    ArrayList<String> res;

    public ArrayList<String> Permutation(String str) {
        //初始化结果集res
        res=new ArrayList<String>();
        char[] arr=str.toCharArray();
        Arrays.sort(arr);
        //字典序添加所有的排列
        res.add(String.valueOf(arr));
        while(next(arr)){
            res.add(String.valueOf(arr));
        }
        return res;
    }

    private boolean next(char[] arr){
        //从后往前,找到第一个递增的索引
        int i=arr.length-2;
        while(i>=0&&arr[i]>=arr[i+1]){
            i--;
        }

        //如果i小于0,说明是一个完全非递增排列,已经到最后一个排列
        if(i<0) return false;

        //从后往前,找到第一个大于arr[i]的元素所在下标
        int j=arr.length-1;
        while(j>0&&arr[j]<=arr[i]){
            j--;
        }

        //交换i,j位置,从i+1位置反转arr
        swap(arr,i,j);
        reverse(arr,i+1);

        return true;

    }

    //交换下标所在元素
    private void swap(char[] arr,int i,int j){
        char temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    //从start处开始反转
    private void reverse(char[] arr,int start){
        int end=arr.length-1;
        while(start<end){
            swap(arr,start,end);
            start++;
            end--;
        }
    }
}

3.复杂度分析

  • 时间复杂度:由于字符串全排列的总数为图片说明 ,寻找下一个排列均摊的时间复杂度为图片说明,所以时间复杂度为图片说明
  • 空间复杂度:需要额外常数级别的内存空间,所以空间复杂度为图片说明