class Solution {
public:
int numTilePossibilities(string tiles) {
}
};
1079. 活字印刷
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
示例 1：
输入："AAB" 输出：8 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2：
输入："AAABBC" 输出：188
示例 3：
输入："V" 输出：1
提示：
1 <= tiles.length <= 7tiles 由大写英文字母组成原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-19 09:19:25
const mx = 8
var c [mx][mx]int
func init() {
for i := 0; i < mx; i++ {
c[i][0], c[i][i] = 1, 1
for j := 1; j < i; j++ {
c[i][j] = c[i-1][j-1] + c[i-1][j] // 预处理组合数
}
}
}
func numTilePossibilities(tiles string) (ans int) {
counts := map[rune]int{}
for _, ch := range tiles {
counts[ch]++ // 统计每个字母的出现次数
}
f := make([]int, len(tiles)+1)
f[0] = 1 // 构造空序列的方案数
n := 0
for _, cnt := range counts { // 枚举第 i 种字母
n += cnt // 常数优化：相比从 tiles.length() 开始要更快
for j := n; j > 0; j-- { // 枚举序列长度 j
// 枚举第 i 种字母选了 k 个，注意 k=0 时的方案数已经在 f[j] 中了
for k := 1; k <= j && k <= cnt; k++ {
f[j] += f[j-k] * c[j][k]
}
}
}
for _, x := range f[1:] {
ans += x
}
return
}
java 解法, 执行用时: 2 ms, 内存消耗: 39.6 MB, 提交时间: 2023-05-19 09:19:00
class Solution {
private static final int MX = 8;
private static final int[][] c = new int[MX][MX];
static {
for (int i = 0; i < MX; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; // 预处理组合数
}
}
public int numTilePossibilities(String tiles) {
// 注：改成 int[26] 统计可能会快一点点，感兴趣可以试试（下面 DP 跳过 cnt=0 的情况）
var counts = new HashMap<Character, Integer>(); // 统计每个字母的出现次数
for (var c : tiles.toCharArray())
counts.merge(c, 1, Integer::sum); // counts[c]++
var f = new int[tiles.length() + 1];
f[0] = 1; // 构造空序列的方案数
int n = 0;
for (var cnt : counts.values()) { // 枚举第 i 种字母
n += cnt; // 常数优化：相比从 tiles.length() 开始要更快
for (int j = n; j > 0; j--) // 枚举序列长度 j
// 枚举第 i 种字母选了 k 个，注意 k=0 时的方案数已经在 f[j] 中了
for (int k = 1; k <= j && k <= cnt; k++)
f[j] += f[j - k] * c[j][k];
}
int ans = 0;
for (int j = 1; j <= n; j++)
ans += f[j];
return ans;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-19 09:18:47
# 空间优化
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
f = [1] + [0] * len(tiles)
n = 0
for cnt in Counter(tiles).values(): # 枚举第 i 种字母
n += cnt # 常数优化：相比从 len(tiles) 开始要更快
for j in range(n, 0, -1): # 枚举序列长度 j
# 枚举第 i 种字母选了 k 个，注意 k=0 时的方案数已经在 f[j] 中了
for k in range(1, min(j, cnt) + 1):
f[j] += f[j - k] * comb(j, k) # comb 也可以预处理，见其它语言的实现
return sum(f[1:])
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-19 09:18:10
const mx = 8
var c [mx][mx]int
func init() {
for i := 0; i < mx; i++ {
c[i][0], c[i][i] = 1, 1
for j := 1; j < i; j++ {
c[i][j] = c[i-1][j-1] + c[i-1][j] // 预处理组合数
}
}
}
func numTilePossibilities(tiles string) (ans int) {
counts := map[rune]int{}
for _, ch := range tiles {
counts[ch]++ // 统计每个字母的出现次数
}
n, m := len(tiles), len(counts)
f := make([][]int, m+1)
f[0] = make([]int, n+1)
f[0][0] = 1 // 构造空序列的方案数
i := 1
for _, cnt := range counts { // 枚举第 i 种字母
f[i] = make([]int, n+1)
for j := 0; j <= n; j++ { // 枚举序列长度 j
for k := 0; k <= j && k <= cnt; k++ { // 枚举第 i 种字母选了 k 个
f[i][j] += f[i-1][j-k] * c[j][k]
}
}
i++
}
for _, x := range f[m][1:] {
ans += x
}
return
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.6 MB, 提交时间: 2023-05-19 09:17:56
class Solution {
private static final int MX = 8;
private static final int[][] c = new int[MX][MX];
static {
for (int i = 0; i < MX; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; // 预处理组合数
}
}
public int numTilePossibilities(String tiles) {
var counts = new HashMap<Character, Integer>(); // 统计每个字母的出现次数
for (var c : tiles.toCharArray())
counts.merge(c, 1, Integer::sum); // counts[c]++
int m = counts.size(), n = tiles.length();
var f = new int[m + 1][n + 1];
f[0][0] = 1; // 构造空序列的方案数
int i = 1;
for (var cnt : counts.values()) { // 枚举第 i 种字母
for (int j = 0; j <= n; j++) // 枚举序列长度 j
for (int k = 0; k <= j && k <= cnt; k++) // 枚举第 i 种字母选了 k 个
f[i][j] += f[i - 1][j - k] * c[j][k];
i++;
}
int ans = 0;
for (int j = 1; j <= n; j++)
ans += f[m][j];
return ans;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-05-19 09:17:42
# 动态规划，计数dp
# 定义 f[i][j] 表示用前 i 种字符构造长为 j 的序列的方案数。
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
counts = Counter(tiles).values() # 统计每个字母的出现次数
n, m = len(tiles), len(counts)
f = [[0] * (n + 1) for _ in range(m + 1)]
f[0][0] = 1 # 构造空序列的方案数
for i, cnt in enumerate(counts, 1): # 枚举第 i 种字母
for j in range(n + 1): # 枚举序列长度 j
for k in range(min(j, cnt) + 1): # 枚举第 i 种字母选了 k 个
f[i][j] += f[i - 1][j - k] * comb(j, k) # comb 也可以预处理，见其它语言
return sum(f[m][1:])
python3 解法, 执行用时: 400 ms, 内存消耗: 13.5 MB, 提交时间: 2020-11-18 10:29:27
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
self.res = -1
dic = collections.Counter(tiles)
def _backtrack(dic, path):
for i in path:
if path.count(i) > dic[i]:
return
self.res += 1
for i in dic:
_backtrack(dic, path+i)
_backtrack(dic, "")
return self.res