算法題目總結 -- 字元串的全排列

題目描述

輸入一個字元串,按字典序列印出該字元串中字元的所有排列。例如輸入字元串abc,則列印出由字元a,b,c所能排列出來的所有字元串abc,acb,bac,bca,cab和cba。

解題思路

從字元串數組中每次選取一個元素，作為結果中的第一個元素。然後，對剩餘的元素全排列，步驟跟上面一樣。很明顯這是個遞歸處理的過程，一直到最後即可。

代碼

import java.util.Arrays;

public class FullArrangementOfString {
    public static void CompleteArrange(char[] str){
        ArrangeForLoc(str, 0, str.length-1);
    }

    public static void ArrangeForLoc(char[] str, int cursor, int end){
        if (cursor==end){
            System.out.println(Arrays.toString(str));
        }else{
            for (int i=cursor;i<=end;i++){
                if (!swapAccepted(str, cursor, i)){
                    continue;
                }
                swap(str, cursor, i);
                ArrangeForLoc(str, cursor+1, end);
                swap(str, cursor, i);
            }
        }
    }

    public static boolean swapAccepted(char[] array, int target, int end){
        for (int i=target;i<end;i++){
            if (array[i]==array[end]){
                return false;
            }
        }
        return true;
    }

    public static void swap(char[] str, int i, int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }


    public static void main(String[] args) {
        String str = "abb";
        CompleteArrange(str.toCharArray());
    }
}