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