欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指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