Pythonでの文字タイルの可能性

タイルのセットがあり、各タイルに1文字のタイル[i]が印刷されているとします。私たちが作ることができる文字の可能な空でないシーケンスの数を見つけてください。したがって、入力が「AAB」の場合、出力は8になります。シーケンスは「A」、「B」、「AA」、「AB」、「BA」、「AAB」、「ABA」、「BAA」です。

これを解決するには、次の手順に従います-

• カウントされる1つのdfs（）を定義します
• 合計：=0
• 1から26の範囲のiの場合
  • count [i] =0の場合、残りをチェックせずに次の反復に進みます
  • count [i]を1減らし、合計を1増やします
  • sum：=sum + dfs（count）
  • count[i]を1つ増やします
• 合計を返す
• 実際の方法は次のようになります-
• サイズ26のカウント配列を1つ作成し、これに0を入力します
• タイル内の各要素iについて
  • count [i –‘A’+1]を1増やします
• return 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