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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告