Skip to content

Latest commit

 

History

History
73 lines (70 loc) · 1.81 KB

README.md

File metadata and controls

73 lines (70 loc) · 1.81 KB

English Version

题目描述

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

示例1:

 输入:S = "qqe"
 输出:["eqq","qeq","qqe"]

示例2:

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

提示:

  1. 字符都是英文字母。
  2. 字符串长度在[1, 9]之间。
## 解法 ### **Python3** ```python
### **Java**
<!-- 这里可写当前语言的特殊实现逻辑 -->
```java

JavaScript

/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function (S) {
    let res = [];
    let arr = [...S];
    arr.sort();
    let prev = [];
    let record = new Array(S.length).fill(false);
    dfs(arr, 0, prev, record, res);
    return res;
};
function dfs(arr, depth, prev, record, res) {
    if (depth == arr.length) {
        res.push(prev.join(''));
        return;
    }
    for (let i = 0; i < arr.length; i++) {
        if (record[i]) {
            continue;
        }
        // 剪枝
        if (i > 0 && arr[i] == arr[i - 1] && record[i - 1]) {
            continue;
        }
        prev.push(arr[i]);
        record[i] = true;
        dfs(arr, depth + 1, prev, record, res);
        // 回溯
        prev.pop();
        record[i] = false;
    }
}

...