剑指offerDay30----字符串的排列

题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：

方法一：固定第一个字符，然后依次将后面的字符串与前面的交换，那么排列的个数就是除了第一个字符以外，其他字符的排列个数+1。也就是固定一个字符串之后，之后再将问题变小，只需求出后面子串的排列个数就可以得出结果。

方法二：

源码：GitHub源码

方法一：

import java.util.*;
public class Solution {
    ArrayList<String> list = new ArrayList<String>();
    public ArrayList<String> Permutation(String str){
        if(str!=null && str.length()>0){
            Permutation(str.toCharArray(),0);
            Collections.sort(list);
        }
        return list;
    }

    private void Permutation(char[] s,int start){
        if(start == s.length-1){
            if(!list.contains(new String(s)))//将重复的元素删去
            list.add(new String(s));
        }else{
            for(int i = start;i < s.length;++i){
                    swap(s,start,i);
                    Permutation(s,start + 1);
                    swap(s,start,i);
            }
        }
    }

    private void swap(char[] s,int i,int j){
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

方法二：

import java.util.*;
public class Solution {
    ArrayList<String> list = new ArrayList<String>();
    public ArrayList<String> Permutation(String str){
        if(str == null || str.length() == 0){
            return list;
        }
        char[] s = str.toCharArray();
        Arrays.sort(s);
        list.add(new String(s));
        int len = s.length;
        while(true){
            int left = len - 1;
            int right;
            while(left >= 1 && s[left - 1] >= s[left]){
                --left;
            }
            if(left == 0)
                break;
            right = left;
            while(right < len && s[right] > s[left - 1]){
                right++;
            }
            swap(s,left - 1,right - 1);
            reverse(s,left);
 
            list.add(new String(s));
        }
 
        return list;
    }

    private void reverse(char[] s,int k){
        if(s == null || s.length <= k)
            return;
        int len = s.length;
        for(int i = 0;i<((len - k) >> 1);++i){
            int m = k + i;
            int n = len - 1 - i;
            if(m<=n){
                swap(s,m,n);
            }
        }
    }

     private void swap(char[] s,int i,int j){
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}