题目描述

活字印刷

你有一套活字字模tiles，其中每个字模上都刻有一个字母tiles[i]。返回你可以印出的非空字母序列的数目。

注意: 本题中，每个活字字模只能使用—次。

测试用例

用例1：
输入："AAB" 输出：8 解释：可能的序列为"A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

---

用例2：
输入："AAABBC" 输出：188

---

用例3：
输入："V" 输出：1

---

思路

全排列问题 —— [1, 2]和[2, 1]是不一样的，同时要去重，要去重就要先对数据进行排序，字符串也是可以排序的

代码实现

/**
	版本1：不进行预排序，然后在最后进行去重
 */

/**
 * @param {string} tiles
 * @return {number}
 */
var numTilePossibilities = function(tiles) {
    //  用map还是set记录？
    let path = [];
    let res = [];
    let used = new Array(tiles.length).fill(0);

    // 去重需要排序
    // tiles = tiles.split("").sort();
    let traversal = function(tiles, used){
        res.push([...path]);
        for(let i = 0; i < tiles.length; i ++){
            // 看该位置是否已经访问过
            // if(used[i] == 1){
            //     continue;
            // }
            // if(i > 0 && tiles[i] == tiles[i - 1] && used[i - 1] == 0){
            //     continue;
            // }
            if(used[i] == 1){
                continue;
            }
            path.push(tiles[i]);
            used[i] = 1;
            traversal(tiles, used);
            used[i] = 0;
            path.pop();
        }
    }

    traversal(tiles, used);
    const ans = [...new Set(res.map((item) => item.join("")))].map((item) => item.split(""));

    return ans.length - 1;
};

/**
	版本2：进行预排序，在递归过程中完成去重
 */
 
/**
 * @param {string} tiles
 * @return {number}
 */
var numTilePossibilities = function(tiles) {
    //  用map还是set记录？
    let path = [];
    let res = [];
    let used = new Array(tiles.length).fill(0);

    // 去重需要排序
    tiles = tiles.split("").sort();
    let traversal = function(tiles, used){
        res.push([...path]);
        for(let i = 0; i < tiles.length; i ++){
            // 看该位置是否已经访问过
            if(used[i] == 1){
                continue;
            }
            if(i > 0 && tiles[i] == tiles[i - 1] && used[i - 1] == 0){
                continue;
            }
            path.push(tiles[i]);
            used[i] = 1;
            traversal(tiles, used);
            used[i] = 0;
            path.pop();
        }
    }

    traversal(tiles, used);

    return res.length - 1;
};