Pythonで文字列内の母音を逆順に入れ替える方法

文字列内の母音を反転するとは

小文字のみで構成された文字列が与えられたとき、その中に含まれる母音(a・e・i・o・u)だけを逆順に入れ替える問題を考えてみましょう。たとえば、文字列が「hello」の場合、母音は「e」と「o」なので、これらを反転すると結果は「holle」になります。同様に、「programming」の場合は「prigrammong」が出力されます。

解決のための手順

この問題は、次の手順に沿って解くことができます。

• 文字列を走査し、母音の一覧を作成すると同時に、その出現位置(インデックス)も記録します
• 収集した母音のリストを逆順に並べ替えます
• カウンター idx を 0 で初期化します
• i を 0 から文字列の長さ − 1 まで繰り返します
  • i が記録済みのインデックスリストに含まれる場合:
    • 反転後の母音 vowels[idx] を結果に追加します
    • idx を 1 増やします
  • それ以外の場合は、元の文字 string[i] をそのまま追加します
• 最終的なリストを連結して文字列として返します

実装例

以下のPythonコードを見ると、処理の流れがより理解しやすくなります。

class Solution:
   def reverseVowels(self, s):
      chars = list(s)
      index = []
      vowels = []
      for i in range(len(chars)):
         if chars[i] in ['a','e','i','o','u']:
            vowels.append(chars[i])
            index.append(i)
      vowels = vowels[::-1]
      final = []
      ind = 0
      for i in range(len(chars)):
        if i in index:
           final.append(vowels[ind])
           ind += 1
        else:
           final.append(chars[i])
      str1 = ""
      return str1.join(final)

ob1 = Solution()
print(ob1.reverseVowels("hello"))
print(ob1.reverseVowels("programming"))

入力

"hello"
"programming"

出力

holle
prigrammong

計算量と効率化のポイント

このアルゴリズムは文字列を2回走査するため、基本の時間計算量は O(n) です。ただし、上記のコードでは i in index の判定にリストを使っているため、各判定に最大 O(n) かかり、最悪の場合全体で O(n²) になります。

より効率化したい場合は、インデックスをセット(set)に格納すれば判定が O(1) になり、全体の計算量を O(n) に抑えられます。また、文字列の先頭と末尾から中央に向かってポインタを動かし、母音同士を出会い次第入れ替える「両ポインタ(two-pointer)方式」も定番の最適化手法として知られています。