1079. 活字印刷
小于 1 分钟
1079. 活字印刷
- 标签:哈希表、字符串、回溯、计数
- 难度:中等
题目大意
给定一个代表活字字模的字符串 tiles
,其中 tiles[i]
表示第 i
个字模上刻的字母。
要求:返回你可以印出的非空字母序列的数目。
**注意:**本题中,每个活字字模只能使用一次。
解题思路
使用哈希表存储每个字符的个数。然后依次从哈希表中取出对应字符,统计排列个数,并进行回溯。如果当前字符个数为 0
,则不再进行回溯。回溯之后将状态回退。
代码
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