字符串的排列

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

import java.util.*;
public class Solution {
    public ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if(str.isEmpty()) return res;
        char[] array = str.toCharArray(); 
        permutation(array, 0, str.length()-1);
        Collections.sort(res);
        return res;
        
    }
     private  void permutation(char[] array, int l, int r) {
         if(l>=r){
             res.add(new String(array));
             return;
         }
         for(int i = l ; i<=r; i++)
             if(i == l || array[l]!=array[i]){ //包括自交换，位置不变
                 swap(array, l,i);
                 permutation(array,l + 1,r); //从l+1开始
                 swap(array, l,i);
             }
         }
     
    private void swap(char[] str, int i , int j){
        char tmp = str[j];
        str[j] = str[i];
        str[i] = tmp;
    }
         
}

• C++ 代码

class Solution {
public:
    vector<string> res;
    vector<string> Permutation(string str) {
        if(str.empty()) return res;
        _permutation(str, 0);
       sort(res.begin(),res.end());
        return res;
    }
    void _permutation(string str, int begin){
        if(begin == str.size()){
              res.push_back(str);
            return;
        }
            for(int i = begin ; i<str.size();i++){
                if(str[i] == str[begin] && i!=begin)
                    continue;
                swap(str[i], str[begin]);
                _permutation(str, begin + 1);
                //swap(str[i],str[begin]);
        }
    }
};