难度: Medium
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
示例 1：
输入："AAB" 输出：8 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2：
输入："AAABBC" 输出：188
示例 3：
输入："V" 输出：1
提示：
1 <= tiles.length <= 7tiles 由大写英文字母组成运行时间: 28 ms
内存: 16.1 MB
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
cnt = Counter(tiles).values()
n, m = len(tiles), len(cnt) #
# f[i][j] -> 用前i个字符拼接j长度的字符串的个数
f = [[0] * (n + 1) for _ in range(m + 1)]
f[0][0] = 1
# 枚举字符
for i, k in enumerate(cnt, 1):
# 枚举长度
for j in range(n + 1):
# 从第i个字符中选择k个组成j长度的字符串
for c in range(min(j, k) + 1):
f[i][j] += f[i - 1][j - c] * comb(j, c)
return sum(f[m][1:])
这道题可以使用动态规划的方法来解决。首先，我们使用Counter来统计每个字母出现的次数。然后，定义一个二维数组f，其中f[i][j]表示使用前i个不同字母，组成长度为j的字符串的方法数。我们可以通过枚举前i-1个字母组成长度为j-c的字符串，然后从第i个字母中选出c个来组成长度为j的字符串，来更新f[i][j]。最后，将长度为1到n的所有字符串的方法数相加，得到最终结果。
时间复杂度: O(m*n^2)
空间复杂度: O(m*n)
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
cnt = Counter(tiles).values() # 统计每个字母出现的次数
n, m = len(tiles), len(cnt) # n是字符串长度，m是不同字符的数量
f = [[0] * (n + 1) for _ in range(m + 1)] # 初始化动态规划数组
f[0][0] = 1 # 空字符串的组合数为1
for i, k in enumerate(cnt, 1): # 枚举字符
for j in range(n + 1): # 枚举长度
for c in range(min(j, k) + 1): # 从第i个字符中选择c个组成j长度的字符串
f[i][j] += f[i - 1][j - c] * comb(j, c) # 更新动态规划数组
return sum(f[m][1:]) # 返回长度为1到n的所有字符串的方法数之和
在这个动态规划解法中，二维数组f[i][j]表示考虑前i个不同的字母，能够组成长度为j的所有不同字符串的组合数。其中，i代表考虑的不同字母的数量，j代表目标字符串的长度。这种表示方式使我们能够逐步构建解决方案，通过增加字母和调整长度来递推计算最终的结果。
初始化f[0][0]为1是因为使用0个字母可以唯一的方式形成长度为0的字符串（即空字符串）。而对于所有j>0的情况，f[0][j]被初始化为0，因为使用0个字母无法形成任何非零长度的字符串。这样的初始化对于动态规划算法的基准情况至关重要，确保了递推开始时有一个正确的起点。
计算组合数comb(j, c)需要准确和高效。在Python中，可以使用`math.comb`函数来直接计算组合数，该函数是自Python 3.8起提供的，能够有效地计算组合数而不需要手动实现。这不仅保证了计算的正确性，由于它是优化过的，也保证了计算的效率。如果使用早于3.8版本的Python，可能需要自己实现组合数的计算或使用第三方库如`scipy.special.comb`。
使用`min(j, k) + 1`作为迭代的边界条件是基于这样的考虑：我们不能从一个字母中选择超过它出现次数（k）或者当前目标字符串长度（j）的字符数。因此，`min(j, k)`确保了不会选择超过可用数量的字符，而`+1`是因为范围包括从0个字符开始选择，直到最大可用字符数。这种选择在确保不超过字母使用次数的同时也避免了不必要的迭代，提高了效率。