Python中的字母瓷砖可能性

假设我们有一套瓷砖，每块瓷砖上印有一个字母tiles[i]。找出我们可以制作的可能的非空字母序列的数量。因此，如果输入是“AAB”，则输出将是8。因为序列是“A”、“B”、“AA”、“AB”、“BA”、“AAB”、“ABA”、“BAA”

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个dfs()函数，它将接收计数。
  • sum := 0
  • 对于范围1到26的i
    • 如果count[i] = 0，则进行下一次迭代，无需检查其余部分。
    • 将count[i]减1，并将sum加1。
    • sum := sum + dfs(count)
    • 将count[i]加1。
  • 返回sum。
  • 实际方法将类似于：
  • 创建一个大小为26的计数数组，并将其填充为0。
  • 对于tiles中的每个元素i
    • 将count[i – ‘A’ + 1]加1。
  • 返回dfs(count)。

让我们看看下面的实现以更好地理解：

示例

在线演示

class Solution(object):
   def numTilePossibilities(self, tiles):
      count = [0 for i in range(27)]
      for i in tiles:
         count[ord(i)-ord('A')+1]+=1
      return self.dfs(count)
   def dfs(self,count):
      summ = 0
      for i in range(1,27):
         if count[i]==0:
            continue
         count[i]-=1
         summ+=1
         summ+=self.dfs(count)
         count[i]+=1
      return summ
ob = Solution()
print(ob.numTilePossibilities("AAB"))

输入

"AAB"

输出

8

更新于：2020年4月30日

507 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告