剑指offer JZ27

字符串的排列：（动态规划）
首先，C++ STL库中的next_ermutation()函数正好可以完成这个功能。
例如：next_ermutation函数
使用这个函数的代码如下：

    vector<string> Permutation(string str) {
        if (str.empty()) return {};
        sort(str.begin(),str.end());
        vector<string> ans;
        ans.push_back(str);
        while(next_permutation(str.begin(),str.end()))
            ans.push_back(str);

        return ans;
    }

当然，做算法题肯定不能用这个方法， 但可以学习补充下。
之所以用动态规划，是因为我们需要得到最终的组合情况， 而这个问题，一般可以分解为子问题完成：
例如：
{a,b}的组合情况
{a,b,c}的组合情况为：
边界条件是，一个字母，
其余则按照前后，组合

针对重复的字母，如{a,b,c,c}
其中f(c1,f(a,,b,c2)) = f(c2,f(a,b,c1)).
所以在构建关系时，引入一个标记。

class Solution {
public:
    vector<string> Get_perm(string str){
        vector<string> ans;
        //DP边界条件,只有一个的时候
        if (str.size() == 1){
            ans.push_back(str); 
            return ans;
        }
        //---处理标记，用于去重
        vector<string> f_sub;
        stack<char> flag;
        for(int i=str.size(); i>=0; --i)
            if (flag.empty()){
                flag.push(str[i]);
            }else if(str[i] != flag.top()){
                flag.push(str[i]);
            }
        //----计算res(str) = res(char_i) + res(str_sub)
        for(int i=0; i<str.size(); i++){
            if(str[i] == flag.top()){
                //去重
                flag.pop();
                //当前字母
                string char_i = str.substr(i,1);
                //剩余字符串
                string s_1 = str.substr(0,i);
                string s_2 = str.substr(i+1, str.size()-i-1);
                string str_sub = s_1 + s_2;
                //获取剩余字符串的res(str_sub)
                f_sub = Get_perm(str_sub);
                //计算res(str)
                for(int j=0; j<f_sub.size(); j++)
                    ans.push_back(char_i + f_sub[j]);
            }
        }
        return ans;
    }

    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.size()==0) return {};
        //排序确认
        sort(str.begin(), str.end());
        res = Get_perm(str);
        sort(res.begin(), res.end());
        return res;
    }
};

当然还有其他的方法，但本题主要考察和练习动态规划的思想和抽象。