面试题 08.08

Write a method to compute all permutations of a string whose charac­ ters are not necessarily unique. The list of permutations should not have duplicates.

Example1:

Input: S = "qqe" Output: ["eqq","qeq","qqe"] Example2:

Input: S = "ab" Output: ["ab", "ba"] Note:

All characters are English letters. 1 <= S.length <= 9

Solutions

1. dfs with swap and hashmap

2. Construct the permutation inplace and avoid visiting the same character in each searching step by using a hash map.

class Solution {
public:
    vector<string> res;
    void dfs(string & S, int st) {
        if (st == S.size())
            res.push_back(S);
        else {
            vector<int> used(128);
            for (int i = st; i < S.size(); i++) {
                if (used[S[i]]++) continue;
                swap(S[st],  S[i]);
                dfs(S, st + 1);
                swap(S[st], S[i]);
            }
        }
    }
    vector<string> permutation(string S) {
        dfs(S, 0);
        return res;        
    }
};

1. dfs with hash map

2. Avoid duplicates by fetching characters from hash map.

class Solution {
public:
    vector<string> res;
    string path;
    void dfs(unordered_map<char, int> & m, int n) {
        if (path.size() == n)
            res.push_back(path);
        else {
            for (auto & [c, cnt] : m) {
                if (cnt <= 0) continue;
                cnt--;
                path.push_back(c);
                dfs(m, n);
                path.pop_back();
                cnt++;
            }
        }
    }
    vector<string> permutation(string S) {
        unordered_map<char, int> m;
        for (auto c : S) m[c]++;
        dfs(m, S.size());
        return res;        
    }
};