算法题目总结 -- 字符串的全排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串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());
    }
}