题目描述

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

样例

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

输入："AAABBC"
输出：188

注意

• 1 <= tiles.length <= 7
• tiles 由大写英文字母组成。

算法

(暴力递归枚举) $O(n!)$

1. 记录下一共有多少种字母，每种有多少个。
2. 开始递归枚举，每一层选择一种单词，每一层都可以累加答案。
3. 注意边界处理。

时间复杂度

• 最差情况下，如要枚举 $n$ 层，故时间复杂度为 $O(n!)$。

空间复杂度

• 递归需要系统栈，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int ans;
    void dfs(vector<int> &num) {
        ans++;
        for (int i = 0; i < num.size(); i++)
            if (num[i] > 0) {
                num[i]--;
                dfs(num);
                num[i]++;
            }
    }
    int numTilePossibilities(string tiles) {
        unordered_map<char, int> seen;
        vector<int> num;
        for (auto &c : tiles) {
            if (seen.find(c) == seen.end()) {
                seen[c] = num.size();
                num.push_back(0);
            }
            num[seen[c]]++;
        }
        ans = 0;
        dfs(num);
        return ans - 1;
    }
};