剣指offer28:文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.

package Chap2;
import java.util.ArrayList;
import java.util.Collections;
/*
 *        ,                   。       abc,
 *        a,b,c            abc,acb,bac,bca,cab cba。
*/
public class Permutation {
    public ArrayList permutation(String str) {
        ArrayList list = new ArrayList<>();
        if (str == null || str.length() == 0) {
           return list;
        }

        collect(str.toCharArray(), 0, list);
        Collections.sort(list);
        return list;
    }

    public static void collect(char[] chars, int begin, ArrayList list) {
        if (begin == chars.length - 1) {
            //          
            String s = String.valueOf(chars);
            if (!list.contains(s)) {
                list.add(s);
                return;
            }
        }

        for (int i = begin; i < chars.length; i++) {
            swap(chars, i, begin);
            collect(chars, begin + 1, list);
            swap(chars, i, begin);
        }

    }

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

    public static void main(String[] args) {
        Permutation a = new Permutation();
        System.out.println(a.permutation("abc"));
    }
}