1079. 活字印刷

参考1079. 活字印刷 - 力扣（Leetcode），难度分1741。

题目

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

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

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

解题思路

• 哈希表+滚动哈希：因为可能有重复的情况考虑使用哈希表统计,题目只要求得到个数而不要求返回完整结果,考虑使用滚动哈希代字符串统计。
• 计数+回溯：序列组合相当于一颗树,对每个出现的字符计数,在递归时进行回溯,即递归前后分别对字符数量进行减加恢复现场。

哈希表+滚动哈希

class Solution {

    HashSet<Integer> set;
    char[] tc;
    public int numTilePossibilities(String tiles) {
        //考虑使用哈希表
        set = new HashSet<>();
        tc = tiles.toCharArray();
        //只考虑数量 使用滚动哈希优化P=131或37都可通过测试用例
        dfs(0, 0);
        return set.size()-1;
    }

    //pre前面已选字符
    void dfs(int hash,int pre) {
        set.add(pre);
        //选或不选
        for(int i = 0; i < tc.length; i++) {
            if((hash>>i&1) == 0){ //该位置可以选择
                dfs(hash | (1 << i),pre*131 + tc[i]);
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n*n!)，递归的位集合可能性有n!种,每种花费n次遍历,n为字符串tiles长度。
• 空间复杂度：O(n)，哈希表空间复杂度不超过n。

计数+回溯

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] cnt = new int[26]; //计数
        for (char c : tiles.toCharArray()) {
            ++cnt[c - 'A'];
        }
        return dfs(cnt);
    }

    private int dfs(int[] cnt) {
        int res = 0;
        for (int i = 0; i < cnt.length; ++i) {
            if (cnt[i] > 0) {
                ++res;
                --cnt[i];
                res += dfs(cnt);
                ++cnt[i]; //回溯 恢复现场
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n×n!),n为字母种类数。
• 空间复杂度：O(n)，计数数组空间为n。