字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路
hi，又是我笨笨的方法呀
整体是递归的方法，先不考虑字典顺序和重复的情况，注意的是前面这个结点是可以插入到后面的任意位置的
string 的函数真的很方便，知道的太少了，都是现查的呜呜呜

string 取子集 substr(i, len)
string 插入 insert(i, str)
string 比较 str1.compare(str2)
string 逆序 reverse(str.begin(), str.end());

class Solution {
public:
    vector<string> Due(string str)
    {
        vector<string> ans;
        if(str.size() == 1)
            ans.push_back(str);
        else if(str.size() == 2)
        {
            ans.push_back(str);
            reverse(str.begin(),str.end());  
            ans.push_back(str);
        }
        else
        {
            string a(str.substr(0,1));
            string b(str.substr(1));
            vector<string> tVec = Due(b);
            for(int i = 0; i < tVec.size(); i++)
                for(int j = 0; j <= tVec[i].size(); j++)
                {
                    string tString = tVec[i];
                    tString.insert(j, a);
                    ans.push_back(tString);
                }
        }
        return ans;
    }
    vector<string> Permutation(string str)
    {
        vector<string> ans;
        if(str.size() == 0)
            return ans;
        vector<string> tVec;
        tVec = Due(str);
        for(int i = 0; i < tVec.size(); i++)
        {
            for(int j = i+1; j < tVec.size(); j++)
                if(tVec[i].compare(tVec[j]) > 0)
                {
                    string tStr = tVec[i];
                    tVec[i] = tVec[j];
                    tVec[j] = tStr;
                }
            if(i == 0)
                ans.push_back(tVec[i]);
            else
                if(tVec[i].compare(ans.back()) > 0)
                    ans.push_back(tVec[i]);
        }
        return ans;
    }
};