Pythonで一貫性のある文字列の個数をカウントするプログラム

この記事では、Pythonを使って「一貫性のある（consistent）文字列」の個数を数えるアルゴリズムを解説します。

問題の定義

すべて異なる文字で構成された文字列 s と、複数の文字列を含む配列 words が与えられます。words 内の文字列が「一貫性がある」とみなされるのは、その文字列に含まれるすべての文字が s の中にも現れる場合です。このとき、words の中に一貫性のある文字列がいくつ存在するかを求めます。

入力例

s = "px"
words = ["ad", "xp", "pppx", "xpp", "apxpa"]

この場合の出力は 3 になります。「p」と「x」だけで構成されている文字列は ["xp", "pppx", "xpp"] の3つだからです。「ad」には「a」「d」、「apxpa」には「a」が含まれているため、これらは条件を満たしません。

解き方のアプローチ

以下の手順で問題を解くことができます。

• カウンター count を 0 で初期化する。

• words の各単語 words[i] について、その単語を構成する各文字 words[i][j] を順番に調べる。

• もし s に含まれていない文字が1つでも見つかったら、その単語は不適格なので内側のループを抜ける。

• すべての文字が s に含まれていた場合のみ、count を 1 増やす。

• 最後に count を返す。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(s, words):
    count = 0
    for i in range(len(words)):
        for j in range(len(words[i])):
            if words[i][j] not in s:
                break
        else:
            # breakされずにループが完了した = 全文字がsに含まれる
            count += 1
    return count

s = "px"
words = ["ad", "xp", "pppx", "xpp", "apxpa"]
print(solve(s, words))

ポイント：Pythonの for-else 構文

このコードの鍵となるのが、Python特有の for-else 構文です。else ブロックは、break によってループが中断されずに最後まで実行された場合にのみ評価されます。これにより、「1文字も欠けていなかった場合だけカウントする」というロジックを簡潔に書けます。

実行結果

入力

"px", ["ad", "xp", "pppx", "xpp", "apxpa"]

出力

3

計算量について

このアルゴリズムの時間計算量は O(N × M) です。ここで N は words の単語数、M は各単語の平均的な長さを表します。さらに、s をあらかじめセット（set(s)）に変換しておけば、文字の存在確認が O(1) になり、全体の処理をより高速化できます。