JZ27 题解 | #字符串的排列#

题意分析

题意

• 给出一个字符串，需要返回这个字符串的所有的字符按照字典序的全排。（一个很经典的模板题）

前置知识

• DFS的回溯法，这里我默认读者掌握了DFS的基本思想。所以我这里主要来介绍一个什么是回溯法。
  

我们来结合这个图来帮助大家理解什么是回溯法，这里介绍的是一棵二叉树的一个回溯，其实二叉树也是一种特殊的图，所以对于图的一个回溯也可以从这里进行学习领会。我们观察这个图，首先，我们先规定，对于每个节点，我们可以决定访问还是不访问。我们发现，当我们遍历2号节点的时候，我们发现我们还需要继续遍历这个节点的子节点，我们先遍历这个节点的左子树，我们在向下进行传递的时候，我们先将这个2号节点打上访问了的标记，这就代表这个2号节点在它的子节点之前就得到了访问，那么我们还要考虑到这个节点比它的子节点更后得到访问的一种情况。所以我们需要将这个标记清除再遍历一遍。这样，我们就得到了一个全排列了。具体请结合代码进行理解。

• 在我看来，一个全排列就是我们规定每个数字的访问顺序，对于某一个具体的位置，在某一时刻虽然被访问了。但是其实也可能在后面才会被访问，为了考虑到这些情况，我们需要利用回溯法将这个位置恢复成没有被访问的情况。回溯法是算法知识里面一个十分常用且有用的一个考点。掌握这个还是很有必要的。

思路分析

思路一(回溯法模拟全排列）

• 这里要注意的一点是由于有重复的字符，所以我们还需要对我们求出来的字符串进行去重处理。

  class Solution {
  public:
    vector<string> ans;
    map<string,int> mp;
    char c[12];
    int cnt=0;
    bool vis[12]={false};
    // 用dfs模拟全排列
    void dfs(vector<char> tmp){
        // 递归出口
        if(tmp.size()==cnt){
            string now="";
            for(auto s:tmp){
                now+=s;
            }
            // 注意出现重复字符的情况
            if(mp[now]==0)
                ans.push_back(now);
            mp[now]=1;
            return;
        }
        // 利用回溯法处理
        for(int i=1;i<=cnt;i++){  
            if(!vis[i]){
                tmp.push_back(c[i]);
                vis[i]=true;
                dfs(tmp);
                // 进行回溯，恢复成之前的状态
                vis[i]=false;
                tmp.pop_back();
            }
        }
    }
    vector<string> Permutation(string str) {
        for(auto x:str){
            c[++cnt]=x;
        }
        vector<char> temp;
        dfs(temp);
        // 最后按照题目要求字典序排列
        sort(ans.begin(),ans.end());
        return ans;
    }
  };

解法二（库函数处理）

• 熟悉C++的同学应该知道，C++有一个库函数是用来实现全排列的，所以我们可以直接调用那个库函数进行求解即可。

• 代码

  class Solution {
  public:
    vector<string> Permutation(string str) {
        char c[12];
        int cnt=0;
        for(auto x:str){
            c[++cnt]=x;
        }
        vector<string> ans;
        // 直接利用C++的库函数对数组进行全排列
        do{
            string temp="";
            for(int i=1;i<=cnt;i++){
                temp+=c[i];
            }
            ans.push_back(temp);
        }while(next_permutation(c+1,c+1+cnt));
        return ans;
    }
  };