1079. 活字印刷

1079. 活字印刷 #

  • 标签:字符串、回溯
  • 难度:中等

题目大意 #

给定一个代表活字字模的字符串 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
本站总访问量  次  |  您是本站第  位访问者