剑指Offer——字符串的排列

题目描述：

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

输入描述:

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

分析：

全排列。

先从小到大排序。
从后往前找到相邻两个值，左边<右边的。
从后往前找到第一个大于左边的数。
交换倒数第一个大于左边的数和左边的数。
将右边到末尾的数全部翻转。
循环上面2-5步，直到找不到左边<右边的情况。

代码：

 1 class Solution {
 2 public:
 3     vector<string> Permutation(string str) {
 4         vector<string> permutations;
 5         if(str == "") return permutations;
 6         sort(str.begin(), str.end());
 7         do {
 8             permutations.push_back(str);
 9         } while(next_permutation(str.begin(), str.end()));
10         return permutations;
11     }
12 };

 1 class Solution {
 2 public:
 3     vector<string> Permutation(string str) {
 4         vector<string> permutations;
 5         if(str == "") return permutations;
 6         sort(str.begin(), str.end());
 7         permutations.push_back(str);                    // 加入排序后的第一组排列
 8         int strLen = str.length();
 9         int i = strLen - 1;
10         while(true) {
11             int i1 = i--;
12             if(i >= 0 && str[i] < str[i1]) {            // 找到相邻两个值，左边<右边的
13                 int i2 = strLen - 1;
14                 while(!(str[i] < str[i2])) i2--;        // 从后往前找到第一个大于左边的数
15                 swap(str[i], str[i2]);                  // 交换倒数第一个大于左边的数和左边的数
16                 reverse(str.begin() + i1, str.end());   // 将右边到末尾的数全部翻转
17                 permutations.push_back(str);
18                 i = strLen - 1;
19                 continue;
20             }
21             if(i <= 0) break;                           // 数组中没有数左边<右边，排列结束
22         }
23         return permutations;
24     }
25 };