LeetCode JZ38(2021.6.22)

LC剑指 Offer 38. 字符串的排列

class Solution {
public:
    vector<string> rec;
    vector<int> vis;

    void dfs(const string& s, int i, int n, string& perm) {
        if (i == n) {
            rec.push_back(perm);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) continue;
            vis[j] = true;
            perm.push_back(s[j]);
            dfs(s, i + 1, n, perm);
            perm.pop_back();
            vis[j] = false;
        }
    }

    vector<string> permutation(string s) {
        int n = s.size();
        vis.resize(n);
        sort(s.begin(), s.end());
        string perm;
        dfs(s, 0, n, perm);
        return rec;
    }
};

发表评论