C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2021-10-21

class Solution {
public:
    void getString(vector<string>& ans,map<char,int> chMap,string result,char ch,int k)
    {
        if(ch!=' ')
        {
            chMap[ch]--;
            result += ch;
        }
        if(result.length()==k)
        {
            ans.push_back(result);
            return;
        }
        for(auto iter:chMap)
        {
            if(iter.second >0)
                getString(ans,chMap,result,iter.first,k);
        }
    }
    
    vector<string> Permutation(string str) {
        vector<string> ans;
        map<char,int> chMap;
        for(char ch :str)
        {
            if(chMap.count(ch)==0) 
                chMap[ch] = 1;
            else
                chMap[ch]++;
        }
        int k = str.length();
        getString(ans,chMap,"",' ',k);
        return ans;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-11-13

class Solution {
    vector<string> ans;
public:
    vector<string> Permutation(string str) {
        //sort(str.begin(), str.end());
        rec(str, 0, str.size());
        return ans;
    }
    
    void rec(string str, int pos, int size){
        if(pos == size){
            ans.push_back(str);
            return;
        }
        unordered_set<int> temp;
        for(int i = pos; i < size; i++){
            if(i!=pos && str[i] == str[pos])
                continue;
            temp.insert(str[i]);
            swap(str[pos], str[i]);
            rec(str, pos + 1, size);
            //swap(str[pos], str[i]);
        }    
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 420KB, 提交时间: 2021-12-14

class Solution {
public:
    vector<string> Permutation(string str) {
        const int n = str.size();
        vector<bool> canUse(n, true);
        len = n;
        s = str;
        dfs(canUse, "");
        return results;
    }
private:
    void dfs(vector<bool> &canUse, string result) {
        if (result.size() == len) {
            results.push_back(result);
            return;
        }
        char temp;
        for (int i = 0; i < len; i++) {
            if (canUse[i] && s[i] != temp) {
                temp = s[i];
                canUse[i] = false;
                dfs(canUse, result + s[i]);
                canUse[i] = true;
            }
        }
    }
    
    vector<string> results;
    int len;
    string s;
};

C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2022-02-10

class Solution {
public:
    set<string> arrange(string str,int n){
    //  功能:排好前n位
    //  递归设置退出条件
    set<string> res1;
    if(n==0){
        res1.insert("");
        return res1;
    }
    set<string> res = arrange(str,n-1);
    
    //  要str前n-1位形成的组合
    for(auto s:res){
        //  res中字符串长度为n-1,最后一位下标为n-2,故有n种放置方式
        res1.insert(str[n-1]+s);
        for(int i=0;i<n-2;i++){
            res1.insert(s.substr(0,i+1)+str[n-1]+s.substr(i+1));
        }
        res1.insert(s+str[n-1]);
    }
    /*
     1.没建立递归前后的联系 ->  通过return得到中间变量,一直继承
     2.字符串提取某位 不能用[i]?
     3.递归的退出条件  n=-1传入是无法跳出来的， 要提前检验
     */
    return res1;
}

vector<string> Permutation(string str) {
    //  输入字符串,打印字符所有排列
    //  aab:aab aba baa
    //  状态转移：已知前n-1个的组合,最后一个人有n种站法,分别检查加入
    //  递归做的事:得到前一层的结果,在此基础上 重新站队
    set<string> ans=arrange(str,str.size());
    
    vector<string> res;
    
    for(auto s:ans){
        res.push_back(s);
    }
    return res;
}
};

C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2022-02-10

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> v;
        //int i=str.size()
        sort(str.begin(),str.end());
        do{
            v.push_back(str);
        }while(next_permutation(str.begin(),str.end()));
        //v.push_back(str);
        return v;
    }
};