时间限制:1秒 空间限制:32768K
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
我的代码
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> res;
if(str.size()<1 || str.size()>9)
return res;
sort(str.begin(),str.end());
res.push_back(str);
/*next_permutation基本思想,将序列分成3部分,第一部分保持不变,
第二部分只有一个数字并且要与第三部分中某个数字进行交换,交换后第三部分进行逆序排列。
从右往左找出第一对相邻递增对,对中前者即为第二部分。
在第三部分中从右往左找出第一个大于第二部分的数字,与第二部分进行交换后,将第三部分逆序。*/
while(next_permutation(str.begin(),str.end())){
res.push_back(str);
}
return res;
}
};
运行时间:4ms
占用内存:472k
class Solution {
public:
vector<string> Permutation(string str) {
//对于a,b,c,交换a,b后,固定b,求a,c排列,交换回a,b;
//交换a,c后,固定c,求a,b排列,交换回a,c。
vector<string> res;
if(str.size()<1 || str.size()>9)
return res;
change(res,str,0);
sort(res.begin(),res.end());
vector<string>::iterator it=unique(res.begin(),res.end());
res.resize(distance(res.begin(),it));
//res.erase(it,res.end());
return res;
}
void swap(char &a, char &b){
char tmp=a;
a=b;
b=tmp;
}
void change(vector<string> &res, string str, int begin){
if(begin==str.size()-1)
res.push_back(str);
for(int i=begin;i<str.size();i++){
swap(str[begin],str[i]);
change(res,str,begin+1);
swap(str[begin],str[i]);
}
}
};
运行时间:4ms
占用内存:492k
网友评论