题解 | #字符串的排列#

class Solution {
private:
    vector<string> res;
    string cur = "";
public:
    vector<string> Permutation(string str) {
        if(str.length() == 0){
            return {};
        }
        int n = str.length();
        vector<char> rec(n);
        for(int i=0; i<n; i++){
            rec[i] = str[i];
        }
        
        sort(rec.begin(), rec.end());
        
        vector<int> vis(n, 0);
        for(int i = 0; i<n; i++){
            if(i>0 && rec[i] == rec[i-1]){
                continue;
            }
            dfs(rec, vis, n, i);
        }
        return res;
    }
    
    void dfs(vector<char>& rec, vector<int>& vis, int n, int cur_i){
        if(cur.length() >= rec.size()){
            return;
        }
        
        cur.push_back(rec[cur_i]);
        vis[cur_i] = 1;
        
        if(cur.length() == rec.size()){
            res.push_back(cur);
        }
        
        for(int i=0; i<n; i++){
            if(vis[i] == 1){
                continue;
            }
            if(i > 0 && rec[i] == rec[i-1] && vis[i-1] == 0){
                continue;
            }
            dfs(rec, vis, n, i);
        }
        cur.pop_back();
        vis[cur_i] = 0;
    }
    
};