劍指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 中的方框部分），降低時間開銷