剑指offer - 字符串的排列 - JavaScript

题目描述:输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

本题和 Leetcode 中的 No.47 全排列 II类似。

# 题目描述

输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

本题和 Leetcode 中的 No.47 全排列 II类似。

# 解法 1: 回溯 + 集合去重

解法 1 的思路是利用回溯法,拿到解空间上的所有结果。由于原字符串可能会有重复元素,例如 aab,所有可以借助 ES6 中 Set 来过滤重复元素,并返回过滤后的结果。

解空间树如下所示:

代码如下:

// ac地址:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
// 原文地址:https://xxoo521.com/2020-02-13-str-permutation/

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
  if (!s.length) {
    return [];
  }

  const result = [];
  __permutation(s.split(""), 0, result);
  // 利用Set过滤重复结果
  return Array.from(new Set(result));
};

/**
 * 回溯遍历得到所有的结果
 *
 * @param {string[]} strs
 * @param {number} start
 * @param {string[]} result
 */
function __permutation(strs, start, result) {
  if (start === strs.length) {
    result.push(strs.join(""));
    return;
  }

  for (let i = start; i < strs.length; ++i) {
    [strs[i], strs[start]] = [strs[start], strs[i]];
    __permutation(strs, start + 1, result);
    [strs[i], strs[start]] = [strs[start], strs[i]];
  }
}

# 解法 2: 回溯剪枝(推荐)

由于是字符串中重复的元素导致了最终结果的重复,所以在回溯的过程中,可以通过“剪枝”来跳过重复情况的遍历。

以字符串 aac 为例,剪枝的过程如下所示:

代码上的实现是在每次的遍历中,使用 map 来记录元素是否被使用过,如果使用过,那么说明是重复元素,直接跳过。代码实现如下:

// ac地址:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
// 原文地址:https://xxoo521.com/2020-02-13-str-permutation/

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
  if (!s.length) {
    return [];
  }

  const result = [];
  __permutation(s.split(""), 0, result);
  return result;
};

/**
 *
 * @param {string[]} strs
 * @param {number} start
 * @param {string[]} result
 */
function __permutation(strs, start, result) {
  if (start === strs.length) {
    result.push(strs.join(""));
    return;
  }

  const map = {};
  for (let i = start; i < strs.length; ++i) {
    if (map[strs[i]]) {
      // 进行剪枝
      continue;
    }
    map[strs[i]] = true;

    [strs[i], strs[start]] = [strs[start], strs[i]];
    __permutation(strs, start + 1, result);
    [strs[i], strs[start]] = [strs[start], strs[i]];
  }
}

相较于解法 1,解法 2 的优势是:

  • 在遍历过程中实现了滤重,不需要再使用 Set
  • 剪枝剪去了不必要的递归遍历(例如图 2 中的方框部分),降低时间开销

# 更多资料