[剑指 Offer] 38. 字符串的排列

[frdmu]

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

 

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

 

示例:

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

限制：

• 1 <= s 的长度 <= 8

 
 
考察排列的去重问题
解法一：
回溯法。难点在于如何去除重复。

• visited数组用来判断某个位置的字符是否访问过；
• set保存所有结果，自动去重。
  问题就是效率太低。代码如下：

class Solution {
public:
    void backtracing(string s, set<string>& res, vector<int>& visited, string& tmp, int n) {
        if (tmp.size() == n) {
            res.insert(tmp);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                tmp.push_back(s[i]);
                visited[i] = 1;
                backtracing(s, res, visited, tmp, n);
                tmp.pop_back();
                visited[i] = 0;
            }
        }
    }
    vector<string> permutation(string s) {
        set<string> res;
        int n = s.size();
        vector<int> visited(n, 0);
        string tmp = "";

        backtracing(s, res, visited, tmp, n);     
        vector<string> ans;
        for (auto r: res) {
            ans.push_back(r);
        }

        return ans;   
    }
};

解法二：
回溯法。排序去重。代码如下：

class Solution {
public:
    void backtracing(string s, vector<string>& res, vector<int>& visited, string& tmp, int n) {
        if (tmp.size() == n) {
            res.push_back(tmp);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] || (i > 0 && s[i] == s[i-1] && !visited[i-1])) continue; 
            
            tmp.push_back(s[i]);
            visited[i] = 1;
            backtracing(s, res, visited, tmp, n);
            tmp.pop_back();
            visited[i] = 0;
        }
    }
    vector<string> permutation(string s) {
        vector<string> res;
        int n = s.size();
        vector<int> visited(n, 0);
        string tmp = "";

        sort(s.begin(), s.end());
        backtracing(s, res, visited, tmp, n);     

        return res;   
    }
};

Refer:
排列问题（二）