《剑指offer》字符串的排列

题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。结果请按字母顺序输出。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。思路：题意说的很清楚，，就是求这个字符串的全排列，我们知道在标准库里面有一个很方便的函数可以求全排列。但是面试官的本意肯定不会是想考我们会不会这个函数，而是想看看我们怎么亲手来实现，所以我们还有必要学会递归的写法。

但是递归的结果我们要注意排序和去重。

1.使用函数

class Solution{public:vector<string> Permutation(string str){vector<string> ans;if(str=="")return ans;sort(str.begin(),str.end());do{ans.push_back(str);}while(next_permutation(str.begin(),str.end()));return ans;}};

2.递归

class Solution{public:vector<string> Permutation(string str){if(str=="")return ans;Solve(str,0);sort(ans.begin(),ans.end());auto it = unique(ans.begin(),ans.end());ans.erase(it,ans.end());return ans;}void Solve(string str,int beg){if(beg==str.length()){ans.push_back(str);return ;}for(int i = beg; i<str.length(); i++){swap(str[beg],str[i]);Solve(str,beg+1);swap(str[beg],str[i]);}}private:vector<string> ans;};

旁观者的姓名永远爬不到比赛的计分板上。

相关文章：

你感兴趣的文章：

标签云：