面试题38

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

• 1 <= s 的长度 <= 8

Solutions

1. backtrack with counter

class Solution {
public:
    vector<string> res;
    vector<int> m;
    string curs;

    void dfs(string & s) {
        if (curs.size() == s.size())
            res.push_back(curs);
        else {
            for (int c = 0; c < 26; c++) {
                if (m[c] <= 0)
                    continue;
                m[c]--;
                curs.push_back('a' + c);
                dfs(s);
                curs.pop_back();
                m[c]++;
            }
        }
    }
    vector<string> permutation(string s) {
        m =  vector<int>(26);
        for (auto & c : s)
            m[c - 'a']++;
        dfs(s);

        return res;
    }
};

1. backtrack with swap

2. In each recursive call, using numbers(characters) with the same value are forbidden.

3. Since swap could break the continuousness of two numbers, additional steps are required for checking duplicates.

class Solution {
public:
    vector<string> res;

    void dfs(string & s, int st) {
        if (st == s.size()) {
            res.push_back(s);
            return;
        }
        int seen = 0;
        for (int i = st; i < s.size(); i++) {
            if (seen & (1 << (s[i] - 'a')))
                continue;
            seen |= (1 << (s[i] - 'a'));
            swap(s[st], s[i]);
            dfs(s, st + 1);
            // since we are passing reference, this pair of characters needs to be restored.
            swap(s[st], s[i]);
        }
    }
    vector<string> permutation(string s) {
        dfs(s, 0);
        return res;
    }
};

• Or another version based on sorted string, we always choose to swap the current character with the inserted character(first) and do not swap back.

• For example:

  • aabbcc, when the insertion position is 0, there are 3 possible strings.

  • aabbcc

  • baabcc

  • caabbc

  • The ordering of each pair of character doesn't change after the swap operation which is different from that in the previous solution.

class Solution {
public:
    vector<string> res;

    void dfs(string s, int st) {
        if (st == s.size()) {
            res.push_back(s);
            return;
        }
        for (int i = st; i < s.size(); i++) {
            if (i > st && s[i] == s[st])
                continue;
            swap(s[st], s[i]);
            // In order to matain the sorted order, we could not swap back.
            // if we swapped up, then the if statement for deduplication would not work properly.
            // as we cannot swapback, we must pass be value instead of reference.
            dfs(s, st + 1);
        }
    }

    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        dfs(s, 0);
        return res;
    }
};