剑指offer27:按字典序打印出该字符串中字符的所有排列
程序员文章站
2023-11-13 13:41:04
1 题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 输入一个字符串,按字典序打 ......
1 题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。2 思路和方法
固定第一个字符,递归取得首位后面的各种字符串组合;再将第一个字符与后面每一个字符交换,同样递归获得其字符串组合;每次递归都是到最后一位时结束,递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。
3 c++核心代码
去重1
1 class solution { 2 public: 3 vector<string> result; 4 vector<string> permutation(string str) { 5 if(str.length()==0) 6 return result; 7 permutation1(str,0); 8 sort(result.begin(), result.end()); 9 return result; 10 } 11 void permutation1(string str, int begin){ 12 if(begin==str.length()) 13 { 14 result.push_back(str); 15 return; 16 } 17 for(int i = begin; str[i]!='\0'; i++) //每个元素与第一个元素交换 18 { 19 if(i!=begin && str[begin]==str[i]) //去重 20 continue; 21 swap(str[begin], str[i]); 22 permutation1(str, begin+1); //交换后,得到子序列,用函数perm得到子序列的全排列 23 swap(str[begin], str[i]); //最后,将元素交换回来,复原,然后交换另一个元素 24 } 25 } 26 };
去重2 https://www.nowcoder.com/questionterminal/fe6b651b66ae47d7acce78ffdd9a96c7
1 void permutationhelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能 2 { 3 if (k == str.size() - 1) 4 ans.push_back(str); 5 unordered_set<char> us; 6 //sort(str.begin() + k, str.end());//这个我不太懂,我把sort放到最后输出结果 7 for (int i = k; i < str.size(); i++) 8 { 9 if (us.find(str[i]) == us.end()) //只和没交换过的换 10 { 11 us.insert(str[i]); 12 swap(str[i], str[k]); 13 permutationhelp(ans, k + 1, str); 14 swap(str[i], str[k]); 15 } 16 } 17 } 18 19 vector<string> permutation(string str) { 20 vector<string> ans; 21 permutationhelp(ans, 0, str); 22 sort(ans.begin(), ans.end()); 23 return ans; 24 }
4 c++完整代码
1 #include <stdio.h> 2 #include <vector> 3 #include <iostream> 4 #include <string> 5 6 using namespace std; 7 8 void swap(char &a, char &b) { 9 char temp = a; 10 a = b; 11 b = temp; 12 } 13 void permcore(string list, int low, int high, vector<string>& res) { 14 if (low == high && 15 find(res.begin(), res.end(), list) == res.end()) { //去重 16 res.push_back(list); 17 } 18 else { 19 for (int i = low; i <= high; i++) {//每个元素与第一个元素交换 20 if (i == low || list[i] != list[low]) { //去重 21 swap(list[i], list[low]); 22 permcore(list, low + 1, high, res); //交换后,得到子序列,用函数perm得到子序列的全排列 23 swap(list[i], list[low]);//最后,将元素交换回来,复原,然后交换另一个元素 24 } 25 } 26 } 27 } 28 29 vector<string> perm(string str) 30 { 31 vector<string> res; 32 if (!str.empty()) 33 permcore(str, 0, str.size() - 1, res); 34 return res; 35 } 36 37 int main() 38 { 39 vector<string> res; 40 string stdstr = "abb"; 41 res = perm(stdstr); 42 for (auto s : res) 43 cout << s << endl; 44 cout << endl; 45 46 string stdstr2 = "aab"; 47 res = perm(stdstr2); 48 for (auto s : res) 49 cout << s << endl; 50 cout << endl; 51 52 system("pause"); 53 return 0; 54 }
参考资料
https://blog.csdn.net/jarviskao/article/details/76999473