Pythonで解く文字タイル問題：DFSで作れる文字列の組み合わせ総数を求める方法

プログラミングの定番問題のひとつに「文字タイル」があります。各タイルには英大文字が1文字ずつ印字されており、これらを自由に並べて作ることができる空でない文字列の総数を求めます。

例えば、入力が "AAB" の場合、答えは 8 になります。作成可能な文字列は以下の8通りです。

"A"・"B"・"AA"・"AB"・"BA"・"AAB"・"ABA"・"BAA"

アプローチ：DFS（深さ優先探索）とバックトラッキング

この問題は、深さ優先探索（DFS）とバックトラッキングを組み合わせることで効率的に解けます。重要なのは、同じ文字が複数枚あっても「文字ごとの残り枚数」を管理することで、重複する組み合わせを自然に排除できる点です。

dfs関数の手順

• カウント配列 count を引数に受け取る dfs() を定義します。
• 合計値 sum を 0 で初期化します。
• i を 1 から 26 までループします。
  • count[i] が 0 の場合、その文字は残っていないので次の反復へ進みます。
  • count[i] を 1 減らして sum を 1 増やします（この時点で1つの文字列が成立）。
  • sum := sum + dfs(count) として、さらに文字を付け足すケースも再帰的に数えます。
  • count[i] を 1 戻して状態を復元します（バックトラッキング）。
• sum を返します。

メイン処理の手順

• サイズ 27 のカウント配列を作成し、すべて 0 で初期化します（インデックス 1〜26 を使用）。
• tiles の各文字 i に対して、count[ord(i) - ord('A') + 1] を 1 増やします。
• dfs(count) の結果を返します。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

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

このアルゴリズムが正しく動く理由

DFSの各ステップで文字を1つ選ぶたびに、その選択によって新しい文字列が1つ完成すると考えます。さらに再帰呼び出しによって、その文字列を延長したすべてのパターンも網羅的にカウントされます。文字の種類ごとに枚数を管理しているため、"AA"のような同一文字列が二重に数えられることはありません。

計算量の観点では、最悪でも各ステップで最大26種類の文字を選べるため、O(26ⁿ)程度の探索となりますが、タイルの枚数 n が小さい前提の問題なので実用上十分高速です。