Pythonですべての母音を含み子音を含まない部分文字列を検索する方法

問題の概要

小文字のアルファベットのみで構成された文字列が与えられたとします。この文字列から、5つの母音(a、e、i、o、u)をすべて少なくとも1回ずつ含み、かつ子音を一切含まない部分文字列をすべて見つけ出すのが今回の課題です。

例えば、入力として "helloworldaeiouaiunicestring" が与えられた場合、出力は次の7つの部分文字列になります。

• aeiou
• aeioua
• aeiouai
• aeiouaiu
• eioua
• eiouai
• eiouaiu

これらはいずれも母音だけで構成されており、かつ a・e・i・o・u の5種類すべてが含まれている点に注目してください。

解決のためのアルゴリズム

この問題は、連続する母音のかたまり(ブロック)ごとに調べることで効率よく解けます。手順は以下の通りです。

1. 文字列 s の長さを n とします。
2. 開始位置 i を 0 から n-1 まで順に動かし、その都度以下を実行します。
   • 出現した母音を記録するための空の辞書 my_map を用意します。
   • 終了位置 j を i から n-1 まで順に動かします。
     • s[j] が母音でなければ、そこでループを中断します(子音を含む部分文字列は対象外のため)。
     • 母音であれば、my_map[s[j]] = 1 として出現を記録します。
     • my_map のサイズ(= 出現した母音の種類数)が 5 になった時点で、s[i:j+1](i 番目から j 番目までの部分文字列)を出力します。

辞書のキー数が自動的に重複を除いた母音の種類数になるため、「5種類すべてが出現したか」の判定が非常にシンプルになります。

実装例

それでは、上記の手順をPythonで実装してみましょう。

def isVowel(x):
    if x in ['a','e','i','o','u']:
        return True
    return False

def get_substrings(s):
    n = len(s)
    for i in range(n):
        my_map = dict()
        for j in range(i, n):
            if (isVowel(s[j]) == False):
                break
            my_map[s[j]] = 1
            if (len(my_map) == 5):
                print(s[i:j + 1])

s = "helloworldaeiouaiunicestring"
get_substrings(s)

入力

"helloworldaeiouaiunicestring"

出力

aeiou
aeioua
aeiouai
aeiouaiu
eioua
eiouai
eiouaiu

処理のポイント

• 早期終了: 子音を検出した時点で内側のループを break することで、無駄な探索を省いています。これにより、連続する母音ブロックごとに独立して判定できます。
• 辞書による重複管理: 辞書は同じキーに対して値を上書きするだけなので、母音の「種類数」を len(my_map) で即座に取得できます。set() を使っても同様の結果が得られます。
• 計算量: 最悪ケースでは O(n²) となりますが、各開始位置での探索は子音で打ち切られるため、実際のデータでは高速に動作します。