题解 | #字符串的排列#

采用图例中的递归方法。

#include <any>
#include <set>
#include <vector>
class Solution {
  public:
    vector<string> Permutation(string str) {
        vector<string> res, tmpres;
        if (str.length() <= 1) {
            res.push_back(str);
            return res;
        }
        string tmp, cha;
        set<char> rec; // 设置一个集合，用于记录出现过的字符
        for (int i = 0; i < str.length(); i++) {
            if (rec.find(str[i]) != rec.end()) { // 若出现过该字符，则不交换
                continue;
            }
            rec.insert(str[i]);
            tmp = str;
            swap(tmp[0], tmp[i]);
            cha = tmp[0];
            tmp = tmp.substr(1, tmp.length() - 1);
            tmpres = Permutation(tmp);
            for (int j = 0; j < tmpres.size(); j++) {
                tmpres[j].insert(0, cha);
            }
            res.insert(res.end(), tmpres.begin(), tmpres.end());
        }
        return res;
    }
};