题解 | #字符串的排列#

终于看懂字典序算法了，自己动手实现的。
字典序前提，字符之间有顺序关系就像在字典中的一样。
另外，给定的序列最好是最小的排列，就是1234等，那么我们就从小到大遍历。
我们首先要明白，怎么找比1234最小的序列呢，从后缀开始处理，我们希望从右到左，较大的数替换左边小的数，以1234为例，4最大，ok，找它前面较小的3，交换。这就是字典序的基本思想。不懂可以看博客。就是尽可能希望我们下一个序列尽可能小，但是比当前序列大。
代码

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> ret;
        ret.push_back(str);
        int L = str.size();
        int flag,cur;
        while(true){
            flag = L-1;
            cur = L-1;
            while(flag>0 && str[flag] <= str[flag-1]) --flag;
            if(flag == 0) break;
            while(cur>flag-1 && str[cur] <= str[flag-1]) --cur;
            swap(str[flag-1],str[cur]);
            str = reverse(flag,L-1,str);
            ret.push_back(str);
        }
        return ret;
    }

    string reverse(int x, int y,string str){
        while(x<y){
            swap(str[x],str[y]);
            x++;
            y--;
        }
        return str;
    }
};