剑指 Offer 38. 字符串的排列

[MrLeihe]

简介

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：

• 1 <= s 的长度 <= 8

代码实现

方法一：递归 + 剪枝

var permutation = function(s) {
    // 字符串转化成字符数组
    var charList = s.split('')
    var res = []
    var dfs = function(x) {
        // 只剩最后一位元素，不能再有其它情况了，添加到 res
        if(x === charList.length - 1) {
            res.push(charList.join(''))
            return
        }
        // 定义一个 set 用于剪枝
        var set = new Set()
        for(let i = x; i < charList.length; i++) {
            // 剪枝
            if(set.has(charList[i])) continue
            set.add(charList[i])
            swap(charList, i, x)
            dfs(x + 1)
            // 复原
            swap(charList, i, x)
        }
    }

    dfs(0)

    return res
};

// 交换元素
var swap = function(chars, i, j) {
    var temp = chars[i]
    chars[i] = chars[j]
    chars[j] = temp
}