题解 | 字符串的排列

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    void dfs(vector<string>& ans, string str, string& s, int pos, vector<bool>& vis){
        if(pos==str.size()){
            ans.push_back(s);
            return;
        }
        for(int i = 0; i < str.size(); ++i){
            if(vis[i]) continue;
            if(i>0&&!vis[i-1]&&str[i]==str[i-1]) continue;
            vis[i] = true;
            s[pos] = str[i];
            dfs(ans, str, s, pos+1, vis);
            vis[i] = false;
        }
    }
    vector<string> Permutation(string str) {
        // write code here
        sort(str.begin(), str.end());
        vector<string> ans;
        vector<bool> vis(str.size(), false);
        string s = str;
        dfs(ans, str, s, 0, vis);
        return ans;
    }
};

这种Ann的题很容易想到dfs，问题就在于怎么剪枝。

如果没有重复元素，直接每个都跑一遍，去掉前面（更浅层）已经出现过的元素就可以了。

本题的难处就在于有重复的时候，怎么让这个位置不跑重复的。

通过深度只能记录这一次有没有出现过这个元素，想要知道之前有没有相同的元素走过这里必须要外部数据结构记录。

一个很经典的做法是排序后记录前面的相同元素是否想要在这个位置用这个值，如果前面的相同元素在更浅的地方已经使用了，说明这次它不想要在这个位置用这个值，那么当前这个元素就可用。

如果前面相同元素没有出现过，那么它就可能想要这个值，因为按照我们的遍历顺序，它在str中排在当前元素前面，早就有机会使用这个位置，也就是这个位置只排这个值已经被遍历过了，所以不要再遍历，直接跳过。

时间复杂度是O(n*n!)，空间复杂度是O(n*n!)。