剑指offer - 字符串的排列 - JavaScript
剑指offer - 字符串的排列 - JavaScript
心谭博客
发布于 2020-04-21 10:43:53
发布于 2020-04-21 10:43:53
题目描述：输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
本题和 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 中的方框部分），降低时间开销
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录