剑指38题解 | #字符串的排列#

#include <vector>
class Solution {
public:
    // vector<string> sum;
    // void find(string& s, int& id, string& v, vector<int>& vis)
    // {
    //     v+=s[id];
    //     if(id == s.size()-1){
    //         sum.push_back(v);
    //         return;
    //     }
    //     for(int i = id; i < s.size(); ++i)
    //     {
    //         swap(s[id], s[i]);
    //         id +=1;
    //         find(s,id, v, vis);
    //     }
    // }
    vector<string> Permutation(string str) {
        // write code here
        //  写的有问题的递归做法
        // if (str.empty()) {
        //     return sum;
        // }
        // int i = 0;
        // string v;
        // vector<int> vis(str.size(), 0); // 记录遍历过情况
        // find(str, i, v, vis);
        // return sum;

        // // 方法1：偷懒解法，next_permutation全排列接口
        // vector<string> v;
        // sort(str.begin(), str.end());
        // do{
        //     v.push_back(str);
        // }while (next_permutation(str.begin(),str.end())); 
        // return v;

        // 方法2：用过一个剔除一个做法
        set<string> res;
        string s;
        find(res, str, s);
        vector<string> v(res.begin(), res.end());
        return v;
    }
    // 全排序能想到这种方法，脑瓜子真好
    void find(set<string>& res, string str, string s){
        if (str.empty()) res.insert(s);
        for(int i = 0; i < str.size(); ++i) // 每一个位置都有可能剔除
        {
            string tmp = str;
            find(res, tmp.erase(i,1), s+str[i]);// 用过的剔除，剔除的保存在新的组合字符串里面
        }
    }
};