题目陈述

大意：给定一个字符串，求出它的字符的所有排序（元素可能有重复），并且答案按从小到大给出

方法一：做法

算法思路

  • 递归搜索进行搜素，对于第h层，枚举第h个位置，应该填入什么下标的元素
  • 注意：此处因为字符串可能有重复的元素，故我们记录的是下标，因为下标不可能重复（相当于一种没有哈希冲突的哈希函数）
  • 然后我们也需要开一个bool数组来记录哪些下标没有被使用过，确保同一下标只被使用过一次
  • 递归边界条件h==s.size()，因为第h层代表正在枚举第h个位置（即前面h-1个位置已经枚举完毕），所以第h=s.size()层代表前面s.size()-1层都已经枚举完毕
  • 回缩的时候，记得将原来状态恢复即可
  • 时间复杂度,每一层都需要枚举所有数是否能使用，总共需要枚举n层

    代码实现

    class Solution {
public:
  void dfs(int h,string &s,string cur,set &ans,vector &f){
      if(h==s.size()){//递归边界
          ans.insert(cur);//找到一个答案并且插入
          return ;
      }
      for(int i=0;i<s.size();i++){
          if(!f[i]){//当前位置的字符未被使用
              f[i]=1;//则使用
              cur+=s[i];//更新当前字符排序
              dfs(h+1,s,cur,ans,f);//递归下一层
              cur.pop_back();//还原当前字符排序
              f[i]=0;//还原f
          }
      }
  }
  vector Permutation(string str) {
      if(str.empty())return {};
      set ans;//因为题目说str中可能有重复元素，所以需要集合来去重,并且起到从小到大排序作用
      vector f(str.size(),0);//用来标记第i个位置是否已被使用
      string cur;//当前的搜索出来的字符串
      dfs(0,str,cur,ans,f);//进行递归搜索字符串排序
      return vector({ans.begin(),ans.end()});//vector迭代器拷贝初始化，只需要元素的类型一样即可，跟容器无关
  }
};

    思考：是否一定需要用set

  • 肯定有同学在这边会有疑问，set内嵌红黑树，每次维护需要花费的代价，但是如果我们一开始先将str排序一下，是不是就不需要set了呢？或者可以将set换成vector？
  • 答案是显然的，不可以。为什么？因为题目里面的元素可能是重复的，所以最后总的排序个数可能小于（N!）
  • 就算我们先排序，最后求出的答案，在vector中依旧会面临一个去重的问题，依旧需要借助set来执行，所以此处我们set还是不能被替换为vector的

    算法二：做法

    算法思路

  • 我们可以发现，全排列的个数也就刚好个，我们这个算法的时间复杂度也刚好是，可以说，已经是最优的了
  • 此处我们先说算法的复杂度，随后再证明正确性
  • 对于字符串s，递归搜索，对于第h层，依次和下标在[h，s.size()-1]中的元素互换
  • 递归边界为h==s.size()-1，（自己跟自己换此时没有意义）
  • 我们先来看递归代码，顺带证明正确性

    证明：算法正确性

      void dfs(int h,string s,set &ans){
      if(h==s.size()-1){//递归边界
          ans.insert(s);//找到一个排序，并且插入
          return ;
      }
      for(int i=h;i<s.size();i++){//假设原来的元素映射到他的下标，那么我们搜索的是下标的全排序
          swap(s[i],s[h]);
          dfs(h+1,s,ans);//进入下一层递归
          swap(s[i],s[h]);//还原s
      }
  }

    复杂度分析

  • 对于第i层循环，设第i层的时间复杂度为f(i)，不难发现，对于第二层for循环有，，即循环执行n-i次，因为有这么多个位置允许被互换，内层又执行递归第i+1层
  • 不难得出f(size-1)=1，易得,故该算***生成个排序

    互异性证明

  • 接下来只需要证明，递归搜索生成的序列，具有互异性，即两两不同，则该算法正确
  • 反证法
  • 假设可以通过不同的互换，得到两个相同的序列，设前面[0,i-1]个位置的互换都相同，在第i层，互换不同，即i和j换，和i和k换，且,
  • 又，最后的序列相同，后续的交换无法改变前面的位置，则推出
  • 故矛盾，则不存在不同的交换方式，使得两个序列的一样的，证毕
  • 注意：此处下标所生成的排序不是字典序递增！

    动画演示

    图片说明

    代码实现

    C++

    class Solution {
public:
  void dfs(int h,string s,set &ans){
      if(h==s.size()-1){//递归边界
          ans.insert(s);//找到一个排序，并且插入
          return ;
      }
      for(int i=h;i<s.size();i++){//假设原来的元素映射到他的下标，那么我们搜索的是下标的全排序
          swap(s[i],s[h]);
          dfs(h+1,s,ans);//进入下一层递归
          swap(s[i],s[h]);//还原s
      }
  }
  vector Permutation(string str) {
      if(str.empty())return {};
      set ans;//因为题目说str中可能有重复元素，所以需要集合来去重,并且起到从小到大排序作用
      dfs(0,str,ans);//开始搜索字符串
      return vector({ans.begin(),ans.end()});//vector迭代器拷贝初始化，只需要元素的类型一样即可，跟容器无关
  }
};

    python

    递归枚举不要s[i]的permutation，然后再拼接上去,递归边界,空串或者一个字符
    class Solution(object):
  def Permutation(self, ss):
      n=len(ss)
      if n<=1:#递归边界，空串或者一个字符
          return ss
      lst=[]
      for i in range(n):
          s1=ss[i]
          for s2 in self.Permutation(ss[:i]+ss[i+1:]):#递归搜索，不取ss[i]
              new_str=s1+s2# s1和s2拼接成新的排序
              if new_str not  in lst :#如果当前没有这个排序
                  lst.append(new_str)    
      lst=sorted(lst)#字典序，从小到大排序
      return lst