【剑指offer48：字符串的排列（下一次排列的进阶版本）】

此题用到了一道题的思想：“下一次排列”
从最小的字符串开始（因为被排序处理过），也就是说每次得到的字符串都是排列好的，不需要其他算法那样计算重复的字符串。
eg：123 132 213 231 312 321

class Solution {
public:

    bool nextpermutaition(string &s)
    {
        int i=s.size()-2;
        if(s.size()<2){return false;}
        int index=0;
       
        while(i>=0&&s[i]>=s[i+1])//相同的字符没有交换的意义，会造成无线循环，所以要>=才行。
        {
            i--;
        }
        if(i<0){return false;}
        int j=s.size()-1;
        while(j>=0&&s[i]>=s[j])//相同的字符没有交换的意义，会造成无线循环，所以要>=才行。
        {
            j--;
        }
       
            swap(s[i],s[j]);
            reverse(s.begin()+i+1,s.end());
        
       
        return true;
    }
    vector<string> permutation(string s) {
        vector<string>tmp;
        sort(s.begin(),s.end());
        do
        {
            tmp.push_back(s);
        }while(nextpermutaition(s));
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

注意的点：
1、循环的设计 不能越界
2.sort函数的使用
3.这里用到了do while 因为第一次要把排序好的字符串放入，而不能先while（）语句。