跳至主要內容

1079. 活字印刷

ITCharge小于 1 分钟

1079. 活字印刷open in new window

  • 标签:哈希表、字符串、回溯、计数
  • 难度:中等

题目大意

给定一个代表活字字模的字符串 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