题目大意
#
给定一个代表活字字模的字符串 tiles，其中 tiles[i] 表示第 i 个字模上刻的字母。
要求：返回你可以印出的非空字母序列的数目。
**注意：**本题中，每个活字字模只能使用一次。
解题思路
#
使用哈希表存储每个字符的个数。然后依次从哈希表中取出对应字符，统计排列个数，并进行回溯。如果当前字符个数为 0，则不再进行回溯。回溯之后将状态回退。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
ans = 0
def backtrack(self, tile_map):
for key, value in tile_map.items():
if value == 0:
continue
self.ans += 1
tile_map[key] -= 1
self.backtrack(tile_map)
tile_map[key] += 1
def numTilePossibilities(self, tiles: str) -> int:
tile_map = dict()
for tile in tiles:
if tile not in tile_map:
tile_map[tile] = 1
else:
tile_map[tile] += 1
self.backtrack(tile_map)
return self.ans
|