题目:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
分析:
首先,不考虑重复的情况下
固定第一个字符，递归取得首位后面的各种字符串组合；
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合;
递归的出口，就是只剩一个字符的时候，
递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
如:abc,固定a,得a+bc;a+cb;a与b交换,b+ac,b+ca;a与c交换c+ba,c+ab,得到六个结果.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> ret = new ArrayList<String>();
if(str.length()==0)return ret;
char[] array = str.toCharArray();
doArrays(ret,array,0);
Collections.sort(ret);
return ret;
}
public void doArrays(ArrayList<String> ret, char[] array, int state){
if(state == array.length-1){
ret.add(String.valueOf(array));
return;
}
for(int j = state;j<array.length;j++){
swap(array,state,j);
doArrays(ret,array,state+1);
swap(array,j,state);
}
}
public void swap(char[]array,int i,int j){
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
考虑循环时,
如abb,a+bb,a+bb;a与第一个b交换,b+ab,b+ba;a与第二个b交换,b+ab,b+ba.实际结果只有abb,bab,bba三种.
当a固定时,操作的子串是bb,bb交换的结果只有一个;
a与第一个b交换时,得到两个新的解;与第二个b交换的结果与第一个相同;
由此,我们可以判断,如果要交换的字符已经在前面出现过时,就不再交换该字符.那么上面的代码就修改为:
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> ret = new ArrayList<String>();
if(str.length()==0)return ret;
char[] array = str.toCharArray();
doArrays(ret,array,0);
Collections.sort(ret);
return ret;
}
public void doArrays(ArrayList<String> ret, char[] array, int state){
if(state == array.length-1){
ret.add(String.valueOf(array));
return;
}
HashSet<Character> charSet = new HashSet<>();//用来筛选是否出现过相同字符
for(int j = state;j<array.length;j++){
if(j==state||!charSet.contains(array[j])){//如果包含该字符,就不进行交换操作了.
//添加j==state判断是为了遇到类似bbc这样的情况,第一个b固定,不让第二个b和c交换了.导致错误.
charSet.add(array[j]);//把每个出现的字符都加入筛选
swap(array,state,j);
doArrays(ret,array,state+1);
swap(array,j,state);
}
}
}
public void swap(char[]array,int i,int j){
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
