剑指Offer - 字符串的排列(Java实现)

题目描述：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路分析：
本题考察的是回溯法的思想。

代码实现如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if(str == null || str.length() < 1){
            return list;
        }else{
            char[] ch = str.toCharArray();
            process(ch,list,0);
            //Collections.sort(list , new IncreaseByAph());
            Collections.sort(list);
            return list;
        }
    }
    
    public void process(char[] ch , ArrayList<String> list , int i ){
        if(i == ch.length ){
            String str = String.valueOf(ch);
            if( !list.contains(str)){
                list.add(str);
            }
        }
        for(int j = i ; j < ch.length ; j++){
            swap(ch,i,j);
            process(ch,list,i+1);
            swap(ch,i,j);
        }
    }
    //交换位置。
    public void swap(char[] ch , int a , int b ){
        char temp = ch[a];
        ch[a] = ch[b];
        ch[b] = temp;
    }
    
    public class IncreaseByAph implements Comparator<String>{
        public int compare(String str1 , String str2){
            return str1.compareTo(str2);
        }
    }
}