BM58 字符串的排列

题目

数据范围：n < 10n<10
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。

分析

这一题其实类型于56题的全排列组合，需要排列的类型由数字数组变成了字符串。因为字符串也是可遍历的，与56题基本相同。通过回调来实现。

58题

1，需要声明3个变量，分别保存结果，标记，和去重。

    const result = [];
    const has = {};
    const set = new Set();
1
2
3

2，声明dfs方法，这里还是使用了数组来缓存，当数组最大长度等于原始字符的时候，把缓存数组的值变成字符串，取出来，去重之后存到结果数组。

    function dfs(path, str) {
        if (path.length === str.length) {
            const value = path.join('');
            if(!set.has(value)) {
                set.add(value);
                result.push(value);
            }
        }
        for (let i = 0; i < str.length; i += 1) {
            if (!has[i]) {
                has[i] = true;
                path.push(str[i]);
                dfs(path, str);
                has[i] = false;
                path.pop();
            }
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

全部代码

function Permutation(str)
{
    // write code here
    const result = [];
    const has = {};
    const set = new Set();
    function dfs(path, str) {
        if (path.length === str.length) {
            const value = path.join('');
            if(!set.has(value)) {
                set.add(value);
                result.push(value);
            }
        }
        for (let i = 0; i < str.length; i += 1) {
            if (!has[i]) {
                has[i] = true;
                path.push(str[i]);
                dfs(path, str);
                has[i] = false;
                path.pop();
            }
        }
    };
    dfs([], str);
    return result;
    
}
module.exports = {
    Permutation : Permutation
};
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

这样就可以通过啦。