字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

1.这道题可以使用回溯算法求解。
2.首先可以模拟人在写全排列的时候，是将排列中的一个字母取出来作为第一个数字固定好，然后将第二个到最后一个元素进行排列组合。
3.按照这个思路，每次从数组中选出一个元素，并记录其索引，如果该索引达到最大值，说明已经是一个排列好的组合，将其放入结果集后，进行回溯操作。
4.在每层递归空间使用一个set记录已经排到过头部的字符，防止重复。
4.最后将结果集进行排序，使其为字典序。

递归树.png

Java代码实现

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if(str.length() == 0)
            return res;
        char[] chars = str.toCharArray();
        Permutation(chars,0,str.length(),res);
        Collections.sort(res);
        return res;
    }

    public void Permutation(char[] chars,int index,int n,ArrayList<String> res) {
        if(index == n){
            res.add(new String(chars));
            return;
        }

        Set<Character> set = new HashSet<>();

        for (int i = index; i < n ; i++) {
            if(!set.contains(chars[i])){
                swapChar(chars,index,i);
                Permutation(chars,index+1,n,res);
                swapChar(chars,i,index);
                set.add(chars[i]);
            }
        }
    }

    private void swapChar(char[] chars,int i,int j){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

Golang代码实现

func Permutation(str string) []string {
    res := make([]string,0)
    if len(str) == 0{
        return res
    }

    chars := make([]byte,0)

    for i:=0; i<len(str); i++{
        chars =append(chars,str[i])
    }

    PermutationDG(0,len(str),chars,&res)
    sort.Strings(res)
    return res;
}

func PermutationDG(index int,n int,chars []byte,res *[]string){
    if index == n{
        *res = append(*res,string(chars))
        return
    }

    numMap := make(map[byte]int)

    for i:=index; i<n; i++{
        if _,ok := numMap[chars[i]]; !ok{
            chars[i],chars[index] = chars[index],chars[i]
            PermutationDG(index+1,n,chars,res)
            chars[i],chars[index] = chars[index],chars[i]
            numMap[chars[i]] = i
        }
    }
}