38 字符串的排列

牛客

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

示例1

输入："ab"
返回值：["ab","ba"]

示例2

输入："aab"
返回值：["aab","aba","baa"]

示例3

输入："abc"
返回值：["abc","acb","bac","bca","cab","cba"]

示例4 输入："" 返回值：[]

定义一个交换方法，交换数组中两个 char 。从第一个位置开始，当前位置和后面所有元素换一遍，然后下一个位置重复操作。最后一个元素操作完后生成字符串。交换之后要记得换回来。

public class Solution {
    int len;
    HashSet<String> set;
    public ArrayList<String> Permutation(String str) {
        char[] arr=str.toCharArray();
        set=new HashSet<String>();
        len=arr.length;
        permutaion(arr, 0);
        return new ArrayList<>(set);
    }
    
    private void permutaion(char[] arr, int index){
        if(index==len){
            set.add(String.valueOf(arr));
        } else {
            permutaion(arr, index+1);
            for(int i=index+1;i<len;++i){
                permutaion(arr, i, index);
                permutaion(arr, index+1);
                permutaion(arr, i, index);
            }
        }
        
    }
    
    private void permutaion(char[] arr, int i, int j){
        char temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}