剑指38：字符串的排列

传送门

nowcoder
leetcode

题目描述

输入一个长度为 n 字符串，（按字典序）打印出该字符串中字符的所有排列。
例如：输入字符串 abc，按字典序打印出字符串 abc, acb, bac, bca, cab 和 cba。

C++ 代码 - nowcoder

/*
    回溯法，使用 DFS

    1.将字符串从小到大排序，相同的字符排列在一起；
    2.从左到右依次枚举每个字符，每次将它放在一个空位；
    3.对于相同字符，人为定序，避免重复计算：
        dfs 记录一个额外的状态，判断上一个相同数是否被使用
    4.不要忘记递归前和回溯时，对状态进行更新。

    时间复杂度：O(n*n!)
        搜索树中最后一层共 n! 个节点，前面所有层的节点总数相比于最后一层节点数是无穷小量，可以忽略。
        最后一层节点记录方案的计算量是 O(n)，所以总时间复杂度是 O(n*n!)。
*/
class Solution {
public:
    string path;
    vector<string> res;
    vector<bool> visited;

    vector<string> Permutation(string str) {
        path = str;
        visited = vector<bool>(str.size());
        sort(str.begin(), str.end());
        dfs(str, 0);
        return res;
    }

    void dfs(string& s, int idx) {
        if (idx == s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < s.size(); i ++) {
            if (!visited[i]) {
                // 规定访问顺序，可以避免重复：必须使用第1个a以后，才能使用第2个a
                if (i && s[i] == s[i - 1] && !visited[i - 1]) continue;
                visited[i] = true;
                path[idx] = s[i];
                dfs(s, idx + 1);
                path[idx] = ' ';
                visited[i] = false;
            }
        }
    }
};

/*
    思路同上
*/
class Solution {
public:
    vector<string> res;

    vector<string> Permutation(string str) {
        if (str.size() == 0) return {};
        PermutationCore(str, 0, str.size() - 1);
        sort(res.begin(), res.end());
        return res;
    }

    void PermutationCore(string& s, int begin, int end) {
        if (begin == end) {
            res.push_back(s);
            return;
        }

        unordered_map<int, bool> visited;
        for (int i = begin; i <= end; i ++) {
            if (visited[s[i]]) continue;
            visited[s[i]] = true;
            swap(s[i], s[begin]);
            PermutationCore(s, begin + 1, end);
            swap(s[i], s[begin]);
        }
    }
};

/*
    库函数 next_permutation: 按照字典序产生排列，依次增大直到最大字典序。
*/
vector<string> Permutation(string str) {
    if (str.size() == 0) return {};

    vector<string> res;
    sort(str.begin(), str.end());
    do {
        res.push_back(str);
    } while (next_permutation(str.begin(), str.end()));

    return res;
}

C++ 代码 - leetcode

/*
    回溯法，使用 DFS
*/
class Solution {
public:
    string path;
    vector<bool> st;
    vector<string> res;

    vector<string> goodsOrder(string s) {
        path.clear();
        res.clear();
        st = vector<bool>(s.size());

        sort(s.begin(), s.end());
        dfs(s);
        
        return res;
    }

    void dfs(string& s) {
        if (path.size() == s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < s.size(); i ++) {
            if (!st[i]) {
                // 规定访问顺序，避免重复元素：必须使用第一个字母后，才能使用第二个字母
                if (i && s[i] == s[i - 1] && !st[i - 1]) continue;
                st[i] = true;
                path.push_back(s[i]);
                dfs(s);
                path.pop_back();
                st[i] = false;
            }
        }
    }
};

参考资料

• leetcode46. 全排列
• leetcode47. 全排列II