[C++知识库]剑指 Offer 38. 字符串的排列

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

解法无非就是把这个字符串的全排列依次放入一个集合当中，因为可能有重复值的情况出现。

解法1.DFS解全排列

class Solution {
public:
    vector<string> ans;
    set<string> se;
    vector<string> permutation(string s) {
        int len = s.length();
        if (len == 0) return ans;
        dfs(s, 0, len);
        set<string>::iterator it;
        for (it = se.begin(); it != se.end(); ++it) {
            ans.push_back(*it);
        }
        return ans;
    }
    void dfs(string &s, int n, int len) {
        if (n == len) {
            se.insert(s);
            return;
        }
        int m = s.length();
        for (int i = n; i < m; ++i) {
            char c = s[n];
            s[n] = s[i];
            s[i] = c;
            dfs(s, n+1, len);
            c = s[n];
            s[n] = s[i];
            s[i] = c;
        }
    }
};

解法2.next_permutation解全排列（雾）——C++STL胜利法

记得对string排序一下，因为next_permutation是从当前值排到最大值(string对应的最大值是字典序最大)

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        int len = s.length();
        if (len == 0) return ans;
        set<string> se;
        sort(s.begin(), s.end());
        do {
            se.insert(s);
        } while (next_permutation(s.begin(), s.end()));
        set<string>::iterator it;
        for (it = se.begin(); it != se.end(); ++it) {
            ans.push_back(*it);
        }
        return ans;
    }
};