38. 字符串的排列

解题思路：

对于一个长度为 n 的字符串（假设字符互不重复），其排列方案数共有：

n×(n−1)×(n−2)…×2×1

排列方案的生成：

根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第 1 位字符（ n 种情况）、再固定第 2 位字符（ n−1 种情况）、… 、最后固定第 n 位字符（ 1 种情况）。

这里是全排列，

重复排列方案与剪枝：

当字符串存在重复字符时，排列方案中也存在重复的排列方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。

递归解析：

1. 终止条件： 当 x = len(c) - 1 时，代表所有位已固定（最后一位只有 1 种情况），则将当前组合 c 转化为字符串并加入 res ，并返回；
2. 递推参数： 当前固定位 x ；
3. 递推工作： 初始化一个 Set ，用于排除重复的字符；将第 x 位字符与 字符分别交换，并进入下层递归；
   1. 剪枝： 若c[i] 在 Set 中，代表其是重复字符，因此 “剪枝”
   2. 将 c[i] 加入 Set ，以便之后遇到重复字符时剪枝
   3. 固定字符： 将字符 c[i] 和 c[x] 交换，即固定 c[i] 为当前位字符
   4. 开启下层递归： 调用 dfs(x + 1)，即开始固定第 x + 1 个字符
   5. 还原交换**： 将字符 c[i] 和 c[x]** 交换（还原之前的交换）

下图中 list 对应文中的列表 c 。
新建 Microsoft PowerPoint 演示文稿.pptx

复杂度分析：

时间复杂度 ：O(N!N)

• N 为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 ，即复杂度为 O(N!) ；字符串拼接操作 join() 使用 O(N) ；因此总体时间复杂度为 O(N!N) 。

空间复杂度 ：O(N)

代码

1. 
   

   const permutation = function (s) {
   const res = [];       // 结果集
   let c = s.split('');  // 字符串转字符数组
   // 从x位开始固定
   const dfs = function (x) {
    // 递归出口，固定到了最后一位
    if (x == c.length - 1) {
      res.push(c.join(''));      // 添加排列方案
      return;
    }
    let set = new Set();
    for (let i = x; i < c.length; i++) {
      if (set.has(c[i])) {
        continue;      // 重复，因此剪枝
      }
      set.add(c[i]);
      swap(i, x);    // 交换，将 c[i] 固定在第 x 位
      dfs(x + 1);    // 开启固定第 x + 1 位字符
      swap(i, x);    // 恢复交换(交换的回溯???不太好想)
    }
   }
   function swap(a, b) {
    [c[a], c[b]] = [c[b], c[a]];
   }
   dfs(0);
   return res;
   }

简明方法

1. 结果数组用 Set ，可以直接去重
   1. 但注意，添加的过程中没有剪枝，性能就不是很好
   2. 这里是最后结果剪枝，所以空间消耗也大一点

2. visit还是用对象来做，访问也可以O(1)

   1. 如果添加过之前访问的

      const permutation = function (s) {
      const res = new Set()
      const visit = {}
      function dfs(path) {
      // 递归出口，当前的长度已经满足了
      if (path.length === s.length) {
        return res.add(path)
      }
      
      for (let i = 0; i < s.length; i++) {
      if (visit[i]) continue; // 
      visit[i] = true;                
      dfs(path + s[i]);                // 添加路径
      visit[i] = false;                // 回溯        
      }
      }
      dfs('')
      return [...res]
      };