题目描述

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

解题思路

用递归的方法进行：

1、先固定首字符，然后递归获得首字母之后的字符串，可以把后面的看成一个新的字符串；

2、然后可以把首字母与后面的字符串交换，但是存在aba这种情况，会有重复，为了避免这种重复，碰到a=a的情况，不进行交换。

代码

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> array;  //创建存储的数组
        if(str.length() == 0)
            return array;
        Permutation(array, str, 0);
        sort(array.begin(), array.end());
        return array;
        
    }
    
    void Permutation(vector<string> &array, string str, int begin){
        if(begin == str.length()-1){
            array.push_back(str);    //递归结束条件
        }
        for(int i = begin; i < str.size(); i++){
            if(i != begin && str[i] == str[begin])
                continue;    //不进行交换的条件，如果没有 i != begin条件，在aa情况下会返回空数组
            swap(str[begin], str[i]);    //交换字符串
            Permutation(array, str, begin+1);  //进行下一轮交换
            swap(str[begin], str[i]); //需要将交换过的数组复原
        }
    }
    
    //交换函数
    void swap(char &p, char &q){
        char temp = p;
        p = q;
        q = temp;
    }
};