題目:
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

分析:
首先,不考慮重復(fù)的情況下
固定第一個字符，遞歸取得首位后面的各種字符串組合；
再把第一個字符與后面每一個字符交換，并同樣遞歸獲得首位后面的字符串組合;
遞歸的出口，就是只剩一個字符的時候，
遞歸的循環(huán)過程，就是從每個子串的第二個字符開始依次與第一個字符交換，然后繼續(xù)處理子串。
如:abc,固定a,得a+bc;a+cb;a與b交換,b+ac,b+ca;a與c交換c+ba,c+ab,得到六個結(jié)果.

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;
    }
}

考慮循環(huán)時,
如abb,a+bb,a+bb;a與第一個b交換,b+ab,b+ba;a與第二個b交換,b+ab,b+ba.實(shí)際結(jié)果只有abb,bab,bba三種.
當(dāng)a固定時,操作的子串是bb,bb交換的結(jié)果只有一個;
a與第一個b交換時,得到兩個新的解;與第二個b交換的結(jié)果與第一個相同;
由此,我們可以判斷,如果要交換的字符已經(jīng)在前面出現(xiàn)過時,就不再交換該字符.那么上面的代碼就修改為:

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<>();//用來篩選是否出現(xiàn)過相同字符

        for(int j = state;j<array.length;j++){
            if(j==state||!charSet.contains(array[j])){//如果包含該字符,就不進(jìn)行交換操作了.
            //添加j==state判斷是為了遇到類似bbc這樣的情況,第一個b固定,不讓第二個b和c交換了.導(dǎo)致錯誤.
                charSet.add(array[j]);//把每個出現(xiàn)的字符都加入篩選
                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;
    }
}