指定された文字から作成できる単語をすべて出力するPythonプログラム

このチュートリアルでは、与えられた文字のリストを使って作成できるすべての単語を見つけて出力する方法を解説します。まずはテストケースを通して、やりたいことを具体的にイメージしましょう。

入力:
words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]

出力:
hi
bye

この例では、「hi」と「bye」は characters リストに含まれる文字だけで構成されているため出力されます。一方、「hello」には必要な「l」が2つあるのにリストには1つもなく、「good」に必要な「g」「o」「d」もリストに存在しないため、これらは出力されません。

重要なのは、単語に含まれる各文字がリスト内に必要な回数だけ存在することを確認する点です。それでは、以下の手順でこの問題を解いていきましょう。

アルゴリズム

1. words(単語リスト)と characters(文字リスト)を初期化する。
2. 単語内の各文字の出現回数を辞書として返す関数を作成する。
   2.1. 空の辞書を用意する。
   2.2. 単語を1文字ずつ調べ、すでに辞書にあればカウントを+1、なければ1で登録する。
   2.3. ループ終了後、辞書を返す。
3. words リストの各単語について次の処理を行う。
   3.1. フラグ変数 flag を 1 で初期化する。
   3.2. 手順2の関数で文字カウントを取得する。
   3.3. 取得した辞書の各キー(文字)について調べる。
      3.3.1. その文字が characters に存在しない場合は flag を 0 にする。
      3.3.2. 存在する場合は、characters 内の出現回数と辞書のカウントを比較し、一致しなければ flag を 0 にする。
   3.4. 最終的に flag が 1 のままなら、その単語を出力する。

実装例

それでは、上記のアルゴリズムを実際にコードにしてみましょう。

## リストの初期化
words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]

## 各文字の出現回数を辞書で返す関数
def char_count(word):
    ## 空の辞書を初期化
    counts = {}
    ## 各文字の出現頻度を数えるループ
    for char in word:
        ## すでに登録されていれば+1、なければ1で登録
        counts[char] = counts.get(char, 0) + 1
    ## 辞書を返す
    return counts

## words リストを反復処理
for word in words:
    ## flag を 1 で初期化
    flag = 1
    ## char_count() 関数で文字カウントを取得
    chars = char_count(word)
    ## 各文字についてチェック
    for key in chars:
        ## キーが characters に存在するか確認
        if key not in characters:
            ## 存在しなければ flag を 0 に更新
            flag = 0
        else:
            ## characters 内の個数と辞書のカウントを比較
            if characters.count(key) != chars[key]:
                ## 個数が足りなければ flag を 0 に更新
                flag = 0
    ## flag が 1 のままなら単語を出力
    if flag == 1:
        print(word)

出力

このプログラムを実行すると、次の結果が得られます。

hi
bye

コードのポイント

dict.get() の活用: counts.get(char, 0) + 1 と書くことで、「キーが存在すればその値を、存在しなければデフォルト値 0 を返す」という処理を1行で実現できます。if 文で分岐するよりも簡潔に書けます。

フラグによる判定: 各単語ごとに flag を 1 で開始し、条件を満たさない文字が1つでも見つかった時点で 0 に切り替えます。ループ完了後に flag が 1 のままなら、その単語は指定された文字だけで作れることになります。

重複文字の扱い: 「hello」のように同じ文字が複数回登場する単語では、文字の有無だけでなく、リスト側の個数との一致まで確認している点が重要です。

別のアプローチ:collections.Counter を使う

標準ライブラリの collections.Counter を使うと、同じ処理をもっと簡潔に書くことができます。

from collections import Counter

words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]

## 利用可能な文字のカウンターを作成
available = Counter(characters)

for word in words:
    ## 必要な文字から利用可能な分を引いて空になれば作成可能
    if not (Counter(word) - available):
        print(word)

Counter 同士の引き算では、左辺のカウントから右辺のカウントが差し引かれ、負の値は自動的に削除されます。その結果が空(すべての文字が必要な分だけ揃っている)であれば、その単語は指定された文字で作成できると判断できます。

まとめ

今回は、文字カウント用の辞書を作成して各単語を検証する基本的な方法と、Counter を使ったより Pythonic な書き方の2通りを紹介しました。単語数を N、単語の長さを L、文字リストの長さを C とすると、基本のアプローチの計算量はおおよそ O(N × L × C) 程度になります。扱うデータが多い場合は Counter 版の方が効率的なので、用途に応じて使い分けるとよいでしょう。

チュートリアルの内容について不明な点があれば、コメント欄でお気軽に質問してください。