题目描述:输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
本题和 Leetcode 中的 No.47 全排列 II类似。
输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
本题和 Leetcode 中的 No.47 全排列 II类似。
解法 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]];
}
}
由于是字符串中重复的元素导致了最终结果的重复,所以在回溯的过程中,可以通过“剪枝”来跳过重复情况的遍历。
以字符串 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 的优势是: