【中等】剑指 Offer 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

限制：

1 <= s 的长度 <= 8

通过次数46,113提交次数84,766

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

暴力，无剪枝

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function(s) {
  if (s.length <= 0) return [];
  src = s.split('');
  let res = [];
  let now = [];
  dfs(src, now, res);
  return res;
};
function dfs(src, now, res) {
  let tmp = src.slice();
  let len = tmp.length;
  if (len <= 0) {
    let str = now.join('');
    res.indexOf(str) < 0 && res.push(str);
    return ;
  }
  for (let i = 0; i < len; i++) {
    let c = tmp.splice(i, 1);
    if (now.indexOf(c) >= 0) continue;
    now.push(c);
    dfs(tmp, now, res);
    tmp.splice(i, 0, now.pop());
  }
}

有剪枝，数据原地交换，速度快很多

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function(s) {
  if (s.length <= 0) return [];
  let c = s.split('');
  let res = [];
  dfs(0, c, res);
  return res;
};
function swap(c, i, j) {
  let temp = c[i];
  c[i] = c[j];
  c[j] = temp;
}
function dfs(x, c, res) {
  if (x === c.length - 1) {
    res.push(c.join(''));
    return ;
  }
  let hash = {};
  // 前面的已经固定了位置了
  for (let i = x; i < c.length; i++) {
    if (hash[c[i]]) continue;
    hash[c[i]] = true;
    // 把当前选择固定在x的位置
    swap(c, i, x);
    dfs(x + 1, c, res);
    // 恢复之前的状态，进行下一个选择
    swap(c, i, x);
  }
}