全排列

LeetCode

输入一个长度为n的字符串，输出该字符串中字符的全排列

解法一

使用递归，但是这样会出现重复的，需要做去重处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const permutation = (str) => {
  const result = [];

  // 用来交换数组的两个位置上的值
  const swap = (arr, start, end) => {
    const tmp = arr[start];
    arr[start] = arr[end];
    arr[end] = tmp;
    return arr;
  };

  // 开始执行递归逻辑
  // arr是当前传入的字符串数组
  // begin是当前开始处理的位置，开始为0
  const run = (arr, begin) => {
    if (begin === arr.length) {
      // 当begin累加到当前最大值时，将其输出
      res.push(arr.join(''));
    } else {
      for (let i = begin; i < arr.length; i++) {
        swap(arr, i, begin);
        run(arr, begin + 1);
        swap(arr, i, begin);
      }
    }
  };

  run(str.split(''), 0);
  return Array.from(new Set(res));
};
console.log(permutation('123'))
// 输出
// [ '123', '132', '213', '231', '321', '312' ]

说明：
使用123举列

  1. 第一个swap说明，将每一位的值和第一位交换位置
    第一层循环会得到这些结果
    1xx、2xx、3xx

  2. 1xx：后，开始执行递归函数run，
    这个时候继续走逻辑，begin变为1，递归后循环结果: 123，接着继续递归，发现begin === arr.length，这个时候输出123，本次递归结束
    回到for循环，这个时候swap，132，继续递归，有发现begin === arr.length，这个时候输出132
    至此1xx后的for循环和递归结束

  3. 后续的2xx和3xx，同理上述1xx的描述

解法二

基于上述的解法，如果传入的字符串是abb，则会出现重复的排列值，需要做去重，上述方法，使用了new Set方法对数组做去重，那能否有方法不需要去重就能实现了，同时也不增加额外的空间开销，同时算法的时间复杂度也最小

不断地计算当前字符串的字典序中下一个更大的排列，直到不存在更大的排列为止即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const permutation = function (s) {
  const res = [];

  const arr = Array.from(s).sort();

  res.push(arr.join(''));

  const swap = (arr, i, j) => {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  };

  const reverse = (arr, start) => {
    let left = start,
      right = arr.length - 1;
    while (left < right) {
      swap(arr, left, right);
      left++;
      right--;
    }
  };

  const nextPermutation = (arr) => {
    let i = arr.length - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) {
      i--;
    }
    if (i < 0) {
      return false;
    }
    let j = arr.length - 1;
    while (j >= 0 && arr[i] >= arr[j]) {
      j--;
    }
    swap(arr, i, j);
    reverse(arr, i + 1);
    return true;
  };

  while (nextPermutation(arr)) {
    res.push(arr.join(''));
  }

  return res;
};
console.log(permutation('123'))
// 输出
// [ '123', '132', '213', '231', '312', '321' ]

解法三

使用深度优先遍历（dfs）

当然该解法，没有去重，还需要加个去重处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const permutation = (nums) => {
  const res = [];
  const len = nums.length;
  if (len === 0) {
    return res;
  }

  const depth = 0;
  const path = [];
  const used = {};

  dfs(nums, len, depth, path, used, res);

  return res;
};

const dfs = (nums, len, depth, path, used, res) => {
  if (len === depth) {
    res.push([...path]);
    return;
  }

  for (let i = 0; i < len; i++) {
    if (used[nums[i]]) {
      continue;
    }
    used[nums[i]] = true;
    path.push(nums[i]);
    dfs(nums, len, depth + 1, path, used, res);
    path.pop();
    used[nums[i]] = false;
  }
};

console.log(permutation('123'))

总结

可以看到输出结果和解法一都不一样

解法一：[ '123', '132', '213', '231', '321', '312' ]
解法二：[ '123', '132', '213', '231', '312', '321' ]

第二种解法是基于字典序的递归查找，这样查找出来的结果，不仅没有重复，而且按字典序进行排序，不需要再进行排序

第一种解法基于遍历的递归交换查找，必然没有任何顺序，但是同样也能很快的找出所有的结果，但势必会有重复的

耗时测试

1
2
3
4
5
6
7
8
const a = '0123456789';
console.time();
console.log(方案二(a).length);
console.timeEnd();

console.time();
console.log(方案一(a).length);
console.timeEnd();

执行输出

1
2
3
4
3628800
default: 1231.317ms
3628800
default: 2406.821ms

由此可见，方案二比方案一，快了1倍

LeetCode