题解 | #字符串的排列#

题意整理

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

方法一（回溯+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.复杂度分析

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