字符串全排列

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

思路

1. 首先，我们固定第一个字符a，求后面两个字符bc的排列
2. 当两个字符bc排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列
3. 现在是把c放在第一个位置的时候了，但是记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍是和原先处在第一个位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处于第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列
4. 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了

Paste_Image.png

class Solution {
public:
    vector<string> result;
    vector<string> Permutation(string str) {
        if(str.length()==0)
            return result;
        
        PermulationImpl(str,0);
        sort(result.begin(),result.end());
        return result;
    }
    
    void PermulationImpl(string str, int begin){
        if(begin==str.length()){
            result.push_back(str);
            return;
        }
        
        for(int i=begin;str[i]!='\0';i++){
            if(i!=begin && str[begin]==str[i])
                continue;
            swap(str[begin],str[i]);
            PermulationImpl(str,begin+1);
            swap(str[begin],str[i]);
        }
    }
};