有重复字符串的排列组合-面试题 08.08

[sl1673495]

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]
示例2:

 输入：S = "ab"
 输出：["ab", "ba"]
提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-ii-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

每轮递归中循环当前剩余的单词，尝试以单词中的每个字母拼接在上次递归后形成的字符串后面，并且用剩下的字母继续递归拼接，直到拼接的长度等于 S 的长度，即可作为一个结果放入 res 中。

注意剪枝部分的逻辑，每轮递归中，假设我们已经尝试过用 q 来拼接了，那么就记录在这轮递归的 visited 中，循环中再遇到 q 直接跳过即可，因为得到的结果一定是重复的。

这个评分结果不是很稳定，不过比较好的时候能跑赢 80% 左右。

/**
 * @param {string} S
 * @return {string[]}
 */
let permutation = function (S) {
    let res = []
    let helper = (prev, rest) => {
        if (prev.length === S.length) {
            res.push(prev)
            return
        }

        let visited = {}
        for (let i = 0; i < rest.length; i++) {
            let char = rest[i]
            if (visited[char]) {
                continue
            }
            visited[char] = true
            helper(prev + char, rest.substring(0, i) + rest.substring(i + 1))
        }
    }
    helper('', S)
    return res
};