Pythonで母音と子音の置き換えにより文字列を別の文字列に変換できるか判定する方法

2つの文字列 s と t が与えられたとします。このとき、任意の位置にある文字は、母音であれば別の母音へ、子音であれば別の子音へのみ置き換えることができます。このルールのもとで、s を t に変換できるかどうか(またはその逆)を判定するのが本記事のテーマです。

問題のポイント

例えば、入力が s = "udpmva"、t = "itmmve" の場合を考えてみましょう。

• u → i(母音 → 母音)
• d → t(子音 → 子音)
• p → m(子音 → 子音)
• a → e(母音 → 母音)

すべての位置で母音同士・子音同士の対応になっているため、出力は True となります。

解法のアプローチ

この問題は、各位置の文字の「種類」(母音か子音か)が一致しているかどうかを確認するだけで解けます。具体的には、以下の手順で進めます。

1. s_size に s の長さを代入します。
2. s_size が t の長さと異なる場合は False を返します。
3. i を 0 から s_size - 1 まで繰り返します。
   • s[i] と t[i] がどちらも母音なら、次の反復へ進みます。
   • s[i] と t[i] がどちらも母音でない(=どちらも子音)なら、次の反復へ進みます。
   • それ以外(片方が母音でもう片方が子音)の場合は False を返します。
4. ループが最後まで完了したら True を返します。

実装例(Python)

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

def solve(s, t):
    s_size = len(s)
    if (s_size != len(t)):
        return False
    for i in range(s_size):
        if (isVowel(s[i]) and isVowel(t[i])):
            continue
        elif ((isVowel(s[i])) == False and (isVowel(t[i]) == False)):
            continue
        else:
            return False
    return True

s, t = "udpgma", "itmmve"
print(solve(s, t))

入力

"udpgma", "itmmve"

出力

True

コードの解説

isVowel() 関数は、渡された文字が a, e, i, o, u のいずれかに該当するかどうかを判定するヘルパー関数です。solve() 関数では、まず両文字列の長さが一致しているかを確認し、その後、各位置ごとに母音・子音の分類が一致しているかを順番にチェックしています。

なお、英語では y が母音として扱われる場合もありますが、この実装ではシンプルに5つの母音のみを対象としています。大文字への対応が必要な場合は、x.lower() を使って判定するとよいでしょう。

計算量

時間計算量は O(n)(n は文字列の長さ)、空間計算量は O(1) です。文字列を一度走査するだけなので、非常に効率的なアルゴリズムといえます。