题解 | #字符串的排列#

1.老版写法

#include <string>
#include <utility>
#include <vector>
class Solution {
public:
    void dfs(unordered_set<string> &res,string &str,int index)
    {
        if(index == str.size()-1)
            res.insert(str);
        else
        {
            for(int i = index;i<str.size();++i)
            {
                swap(str[i],str[index]);
                dfs(res,str,index+1);
                swap(str[i], str[index]);
            }
        }
    }
    vector<string> Permutation(string str) {
        sort(str.begin(),str.end());
        unordered_set<string> res;
        dfs(res,str,0);
        vector<string> result;
        for(auto &r:res)
            result.push_back(r);
        return result;
    }   
};

2.标记法：

思路：

都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复项数字的全排列类似，只是这道题输出顺序没有要求。但是为了便于去掉重复情况，我们还是应该参照数组全排列，优先按照字典序排序，因为排序后重复的字符就会相邻，后续递归找起来也很方便。

使用临时变量去组装一个排列的情况：每当我们选取一个字符以后，就确定了其位置，相当于对字符串中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。

• 终止条件： 临时字符串中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
• 返回值： 每一层给上一层返回的就是本层级在临时字符串中添加的元素，递归到末尾的时候就能添加全部元素。
• 本级任务： 每一级都需要选择一个元素加入到临时字符串末尾（遍历原字符串选择）。

递归过程也需要回溯，比如说对于字符串“abbc”，如果事先在临时字符串中加入了a，后续子问题只能是"bbc"的全排列接在a后面，对于b开头的分支达不到，因此也需要回溯：将临时字符串刚刚加入的字符去掉，同时vis修改为没有加入，这样才能正常进入别的分支。

具体做法：

• step 1：先对字符串按照字典序排序，获取第一个排列情况。
• step 2：准备一个空串暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的字符被加入了。
• step 3：每次递归从头遍历字符串，获取字符加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用，也不需要将其纳入。
• step 4：进入下一层递归前将vis数组当前位置标记为使用过。
• step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入字符串的元素，
• step 6：临时字符串长度到达原串长度就是一种排列情况。

#include <algorithm>
#include <memory>
#include <string>
#include <utility>
#include <vector>
class Solution {
public:
    void recursion(vector<string> &res,string &str,string &temp,vector<int> &vis)
    {
        //临时字符串满了加入输出
        if(temp.size() == str.size())
        {
            res.push_back(temp);
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0;i<str.size();i++)
        {
            //遍历所有元素选取一个加入
            if(vis[i])
                continue;
                /*
                这里vis[i-1]与!vis[i-1]二者皆可，都能通过。两种写法结果集是一样的，只是每一项添加到结果集的时机不同。 
                1. 写visit[i-1] 比如1 2 2这个数组，会导致在（第二层）第一次遍历到中间的2时，遍历到第二个2时，直接跳过了，不会加入到list，在（第三层）第一次遍历2时，此时中间的2已经标记为false，才会加入到list中，答案是对的 
                2. 写!visit[i-1] 与上面相反，这样的含义是：因为数组最开始已经被我们排序，所以相等的数字一定挨着，比如两个2，在处理第二层的时候，前面的2肯定先用，后面的2后用，注意这里“用过”的含义不是遍历过，在用后面2的时候，前面2已经置为false，因此这里用！visit[i-1]代表前面已经用过，而不是遍历过
                */
            //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
            if(i > 0 && str[i-1] == str[i] && vis[i-1])
                continue;
            vis[i] = 1;//标记为使用过 
            temp.push_back(str[i]);//加入临时字符串
            //递归添加下一个字符
            recursion(res, str, temp, vis);
            //回溯
            vis[i] = 0;
            temp.pop_back();
        }
    }
    vector<string> Permutation(string str) {
        //先按字典序排序，使重复字符串相邻
        sort(str.begin(), str.end());
        //标记每个位置的字符是否被使用过
        vector<int> vis(str.size(),0);
        vector<string> res;
        string temp;
        //递归获取
        recursion(res, str, temp, vis);
        return res;
    }   
};