字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
1
2
2
/**
* @param {string} s
* @return {string[]}
*/
var permutation = function(s) {
if(s.length === 1) return [s]
let arr = s.split("")
let len = arr.length
let ans = []
let path = []
function dfs(arr) {
if(path.length === len) {
ans.push(path.join(""))
return
}
if(!arr.length) return
let map = new Map()
for (let i = 0; i < arr.length; i++) {
// 剪枝去重
if(map.has(arr[i])) continue
path.push(arr[i])
map.set(arr[i], 1)
// 下一轮可选字符
let _arr = arr.slice(i+1).concat(arr.slice(0, i))
dfs(_arr)
path.pop()
}
}
dfs(arr)
return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof