剑指offer27：按字典序打印出该字符串中字符的所有排列

1 题目描述

　　输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a，b，c所能排列出来的所有字符串abc，acb，bac，bca，cab和cba。

输入描述:

　　输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

2 思路和方法

　　固定第一个字符，递归取得首位后面的各种字符串组合；再将第一个字符与后面每一个字符交换，同样递归获得其字符串组合；每次递归都是到最后一位时结束，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。

3 C++核心代码

去重1

 class Solution {
 public:
     vector<string> result;
     vector<string> Permutation(string str) {
         if(str.length()==)
             return result;
         permutation1(str,);
         sort(result.begin(), result.end());
         return result;
     }
     void permutation1(string str, int begin){
         if(begin==str.length())
         {
             result.push_back(str);
             return;
         }
         for(int i = begin; str[i]!='\0'; i++)    //每个元素与第一个元素交换
         {
             if(i!=begin && str[begin]==str[i])    //去重
                 continue;
             swap(str[begin], str[i]);
             permutation1(str, begin+);    //交换后,得到子序列,用函数perm得到子序列的全排列
             swap(str[begin], str[i]);    //最后,将元素交换回来,复原,然后交换另一个元素
         }
     }
 };

去重2 https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7

 void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能
 {
     if (k == str.size() - )
         ans.push_back(str);
     unordered_set<char> us;
     //sort(str.begin() + k, str.end());//这个我不太懂，我把sort放到最后输出结果
     for (int i = k; i < str.size(); i++)
     {
         if (us.find(str[i]) == us.end()) //只和没交换过的换
         {
             us.insert(str[i]);
             swap(str[i], str[k]);
             PermutationHelp(ans, k + , str);
             swap(str[i], str[k]);
         }
     }
 }

 vector<string> Permutation(string str) {
     vector<string> ans;
     PermutationHelp(ans, , str);
     sort(ans.begin(), ans.end());
     return ans;
 }

4 C++完整代码

 #include <stdio.h>
 #include <vector>
 #include <iostream>
 #include <string>

 using namespace std;

 void swap(char &a, char &b) {
     char temp = a;
     a = b;
     b = temp;
 }
 void permcore(string list, int low, int high, vector<string>& res) {
     if (low == high &&
         find(res.begin(), res.end(), list) == res.end()) {  //去重
         res.push_back(list);
     }
     else {
         for (int i = low; i <= high; i++) {//每个元素与第一个元素交换
             if (i == low || list[i] != list[low]) {    //去重
                 swap(list[i], list[low]);
                 permcore(list, low + , high, res); //交换后,得到子序列,用函数perm得到子序列的全排列
                 swap(list[i], list[low]);//最后,将元素交换回来,复原,然后交换另一个元素
             }
         }
     }
 }

 vector<string> perm(string str)
 {
     vector<string> res;
     if (!str.empty())
         permcore(str, , str.size() - , res);
     return res;
 }

 int main()
 {
     vector<string> res;
     string stdstr = "abb";
     res = perm(stdstr);
     for (auto s : res)
         cout << s << endl;
     cout << endl;

     string stdstr2 = "aab";
     res = perm(stdstr2);
     for (auto s : res)
         cout << s << endl;
     cout << endl;

     system("pause");
     return ;
 }

参考资料

https://blog.****.net/JarvisKao/article/details/76999473