一、问题描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
二、解题思路
1.本人的解题思路是用arrayList列表当左队列来使用，首先将字符串第一个字符（转换成String）加入到列表中，然后下一个字符开始，将该字符插入到列表中长度为i的任一位置生成新的字符串，然后将该字符串加入到列表中
2.论坛里面有人使用了深度遍历的解法。
三、代码
1.自己的解题方法
import java.util.*;
public class Solution {
private char[] seqs;
private Integer[] book;
private HashSet<String> result=new HashSet<String>();
public ArrayList<String> Permutation(String str) {
ArrayList<String> result=new ArrayList<String>();
if(str==null || str.length()==0)
return result;
result.add(String.valueOf(str.charAt(0)));
for(int i=1;i<str.length();i++){
while(result.get(0).length()==i){
String tmp= result.remove(0);
for(int j=0;j<=tmp.length();j++){
String temp="";
if(j==tmp.length()){
temp=tmp+String.valueOf(str.charAt(i));
}else{
temp=tmp.substring(0,j)+String.valueOf(str.charAt(i))+tmp.substring(j,tmp.length());
}
if(!result.contains(temp))
result.add(temp);
}
}
}
Collections.sort(result);
return result;
}
}2.深度遍历的解法
import java.util.*;
public class Solution {
private char[] seqs;
private Integer[] book;
private HashSet<String> result=new HashSet<String>();
public ArrayList<String> Permutation(String str) {
ArrayList<String> arrange=new ArrayList<String>();
if(str==null || str.isEmpty())
return arrange;
char[] strs=str.toCharArray();
seqs=new char[strs.length];
book=new Integer[strs.length];
for(int i=0;i<book.length;i++)
book[i]=0;
dfs(strs,0);
arrange.addAll(result);
Collections.sort(arrange);
return arrange;
}
private void dfs(char[] arrs,int step){
if(arrs.length==step){
String str="";
for(int i=0;i<seqs.length;i++)
str+=seqs[i];
result.add(str);
return;
}
for(int i=0;i<arrs.length;i++){
if(book[i]==0){
seqs[step]=arrs[i];
book[i]=1;
dfs(arrs,step+1);
book[i]=0;
}
}
}
}
转载请注明原文地址: https://ju.6miu.com/read-34953.html
