首页 > 代码库 > 算法:字符串的排列
算法:字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
写了两种版本,一种为递归,一种为使用stl next_permutation 函数;
1 class Solution { 2 public: 3 void all(vector<string> &v,string s,string str){ 4 if(str.size()==0){ 5 v.push_back(s); 6 return; 7 } 8 for(int i =0;i!=str.size();++i){ 9 //定义a因为不能改变当前层次的s 10 string a; 11 a+=str[i]; 12 string tmp = str; 13 str.erase(str.begin()+i); 14 all(v,s+a,str); 15 str = tmp; 16 } 17 } 18 vector<string> Permutation(string str) { 19 vector<string> v; 20 if(str.size()==0) return v; 21 string s; 22 all(v,s,str); 23 sort(v.begin(),v.end()); 24 auto it = unique(v.begin(),v.end()); //去重 25 v.erase(it,v.end()); 26 return v; 27 } 28 };
class Solution { public: vector<string> Permutation(string str) { vector<string> v; if(str.size()==0) return v; if(str.size()==1){ v.push_back(str); return v; } sort(str.begin(),str.end()); do{ v.push_back(str); }while(next_permutation(str.begin(),str.end())); return v; } };
算法:字符串的排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。