题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路
- 首先，我们固定第一个字符a，求后面两个字符bc的排列
- 当两个字符bc排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列
- 现在是把c放在第一个位置的时候了，但是记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍是和原先处在第一个位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处于第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列
- 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了
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]);
}
}
};
