一、题目描述

JZ27 字符串的排列
题目大意：输入一个字符串, 按字典序打印出该字符串中字符的所有排列
注意审题：可能有重复字符并且需要按照字典序打印出该字符串的所有排列

二、算法1（回溯）

解题思路

  1. 本题是一个经典的全排列的问题, 可以使用回溯算法来解决. 不过与一般的全排列问题不同的地方是它可能有重复字符, 那么按照一般的递归法可能会有多种重复的情况, 例如"aa" 就得到"aa"和"aa"这两种情况
  2. 一种解决的方法就是使用哈希集合来去重, 将所有可能的结果都存放下来, 最后对结果进行排序

图片说明

代码实现（C++11）

class Solution {
public:
    unordered_set<string> st;    // 用于字符串去重
    vector<bool> vis;        // 标记当前访问的字符
    string path;            // 记录当前情况

    vector<string> Permutation(string str) {
        vector<string> ans;
        vis.resize(str.size(), false);    // 初始化为false
        dfs(str);    // 回溯入口
        for(auto & s : st) ans.push_back(s);    // 将结果加入ans数组
        sort(ans.begin(), ans.end());    // 按字典序排序
        return ans;
    }

    void dfs(string& str){
        if(path.size() == str.size()){    // 得到一种排列
            st.insert(path);
            return;
        }

        for(int i = 0; i < str.size(); i++){
            if(vis[i]) continue;    // 若当前字符已经使用过, 跳过
            vis[i] = true;    // 标记为使用
            path.push_back(str[i]);    // 加入结果
            dfs(str);    // 继续递归
            path.pop_back();    // 状态回溯
            vis[i] = false;
        }
    }
};

时间复杂度：O(n!)
空间复杂度：O(n!), 哈希集合最大可能的空间

空间优化

  1. 上面的做法用到了哈希集合这一数据结构来临时存放结果, 消耗了大量的空间. 那么, 有没有办法不用哈希去重呢, 回答是可以的
  2. 我们可以观察到出现大量重复的原因是重复字符相邻, 因此我们需要保证重复字符只会被使用一次, 那么我们可以先对原字符串排序, 这样可以保证相同的字符都相邻, 要保证重复字符只被使用一次, 我们规定每次加入的字符一定是它在重复字符集合里从左往右第一个没用被访问的字符
  3. 并且由于我们先对字符进行了排序, 那么最后的结果就是按字典序排列的, 我们不必再排序了

代码实现（C++11）

class Solution {
public:
    vector<string> ans;
    vector<bool> vis;
    string path;

    vector<string> Permutation(string str) {
        sort(str.begin(), str.end());    // 按字典序排序
        vis.resize(str.size(), false);
        dfs(str);
        return ans;
    }

    void dfs(string& str){
        if(path.size() == str.size()){    // 中止条件
            ans.push_back(path);
            return;
        }

        for(int i = 0; i < str.size(); i++){
            if(vis[i]) continue;    // 若当前字符访问过
            if(i > 0 && vis[i - 1] && str[i - 1] == str[i]) continue;    // 若当前字符不是相同字符集合中从左往右第一个使用的, 跳过
            vis[i] = true;
            path.push_back(str[i]);
            dfs(str);
            path.pop_back();    // 回溯
            vis[i] = false;
        }
    }
};

时间复杂度：O(n!)
空间复杂度：O(n), 用于临时存放当前结果的string所占空间

三、算法2（next_permutation）

解题思路

  1. next_permutation算法可以求出一个排列下个字典序更大的排列, 因此只要我们对字符串排序后不断求出它的下一个排列, 即可得到所有排列
  2. next_permutation算法是思想是: 每次从后往前找到第一个满足a[i] < a[i + 1]的数, 再从[i + 1, n)中找到最接近a[i]并大于a[i]的第一个数a[j], 要得到下一个排列, 我们应该交换a[i]和a[j], 然后让a[j]后的数从小到大排列
  3. 实际上, 我们不必每次都对[i + 1, n)的数都进行排序, 可以发现, 由于a[j]是第一个大于a[i]的数, 故a[j + 1]一定是小于或等于a[i]的, 交换a[i]和a[j]后, [i + 1, n)一定是从大到小的序列, 我们只需要对其进行翻转即可 (以上就是求下一个排列的算法思想)
  4. 当未知道满足条件的i时, 说明此时已经是最大的一个排列了, 返回false即可

代码实现（C++11）

class Solution {
public:
    vector<string> ans;

    vector<string> Permutation(string str) {
        sort(str.begin(), str.end());    // 一定记住要先排序
        do{
            ans.push_back(str);
        } while(nextPermutation(str));
        return ans;
    }

    bool nextPermutation(string& s){
        int i = s.size() - 2;    // 从倒数第二个数开始向左搜寻
        while(i >= 0 && s[i] >= s[i + 1]) i--;    
        if(i < 0) return false;    // 未找到满足条件的i, 返回false
        int j = s.size() - 1;
        while(s[j] <= s[i]) j--;    // 若i存在, 则j一定存在
        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());    // 翻转区间[i + 1, n - 1]
        return true;
    }
};

时间复杂度：O(n!)
空间复杂度：O(1)
C++算法库提供了现成next_permutation函数, 不过面试时考察的重点就是对算法的理解, 一般还是自己实现一下比较好