题解 | #字符串的排列#

回溯算法：加入去重操作

class Solution {
public:
    void dfs(vector<string>& res, vector<bool>& used, string& path, string& str) {
        if (path.length() == str.length()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            if (used[i]) continue;
            if (i > 0 && str[i] == str[i - 1] && !used[i - 1]) continue;
            path.push_back(str[i]);
            used[i] = true;
            dfs(res, used, path, str);
            used[i] = false;
            path.pop_back();
        }
    }

    vector<string> Permutation(string str) {
        sort(str.begin(), str.end());
        vector<string> res;
        string path;
        vector<bool> used(str.length(), false);
        dfs(res, used, path, str);
        return res;
    }
};

n！算法：全排列

class Solution {
public:
    void dfs(unordered_set<string>& hash, string& str, int start) {
        if (start == str.length() - 1) {
            if (!hash.count(str)) hash.insert(str);
            return;
        }
        for (int i = start; i < str.length(); i++) {
            swap(str[i], str[start]);
            dfs(hash, str, start + 1);
            swap(str[i], str[start]);
        }
    }

    vector<string> Permutation(string str) {
        if (str == "") return {""};
        unordered_set<string> hash;
        dfs(hash, str, 0);
        return vector<string>(hash.begin(), hash.end());
    }
};