题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路
1.这道题可以使用回溯算法求解。
2.首先可以模拟人在写全排列的时候,是将排列中的一个字母取出来作为第一个数字固定好,然后将第二个到最后一个元素进行排列组合。
3.按照这个思路,每次从数组中选出一个元素,并记录其索引,如果该索引达到最大值,说明已经是一个排列好的组合,将其放入结果集后,进行回溯操作。
4.在每层递归空间使用一个set记录已经排到过头部的字符,防止重复。
4.最后将结果集进行排序,使其为字典序。
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 } } }