题解 | 字符串的排列

#include <type_traits>
class Solution {
  //和全排列一样的思路
public:
    vector<string> ans;
    vector<string> Permutation(string str) {
        if(str.size() ==0)return {""};

        dp(str, 0);

        return ans;
    }

    void dp(string& str, int index){
        set<char> c;  //因为str中有重复的字符，在进行交换时会把相同的字符多次放到本位，所以用set集合，存储本位已经试过的字符，本位不能再使用了

        if(index == str.size()-1){
            ans.push_back(str);
        }

        for(int i = index; i < str.size(); ++i){
            if( c.count(str[i]) == 0){
                c.insert(str[i]);   //标记本位已经用过
                swap(str[i], str[index]);
                dp(str, index+1);
                swap(str[i], str[index]);
            }
        }

        return;
    }

};