Pythonで文字列内の英字のみを反転する方法

文字列 S が与えられたとき、英字（アルファベット）だけの位置を反転させ、記号や数字などの英字以外の文字は元の位置にそのまま残すという問題を考えてみましょう。

たとえば、入力文字列が "a-bC-dEf-ghIj" の場合、出力は "j-Ih-gfE-dCba" となります。ハイフン「-」の位置は変わらず、英字部分だけが逆順に入れ替わっているのがポイントです。

解決のアプローチ

この問題は、いわゆる2ポインタ法（two-pointer technique）を使うことで効率的に解けます。先頭から走査するインデックスと、末尾から走査するインデックスの2つを用意し、両側の文字がどちらも英字であれば入れ替える、という流れです。

具体的な手順は以下の通りです。

• S が空文字列の場合は、そのまま S を返す。
• 結果を格納する文字列 str_ を空で初期化し、index1 = 0（先頭側）、index2 = len(S) - 1（末尾側）とする。
• index1 < len(S) の間、以下を繰り返す。
  • index2 >= 0 かつ S[index1] と S[index2] の両方が英字の場合：
    str_ に S[index2] を追加し、index2 を1減らして index1 を1増やす。
  • S[index1] が英字だが S[index2] が英字でない場合：index2 を1減らす（対応する英字を探す）。
  • S[index1] が英字でない場合：str_ に S[index1] をそのまま追加し、index1 を1増やす。
  • 上記以外の場合：index2 を1減らし、index1 を1増やす。
• ループ終了後、str_ を返す。

なお、文字が英字かどうかの判定には、Python標準の文字列メソッド isalpha() を利用します。正規表現モジュール re を使う方法もありますが、isalpha() の方がシンプルで読みやすい実装になります。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def reverseOnlyLetters(self, S):
        if not S:
            return S
        str_ = ""
        index1 = 0
        index2 = len(S) - 1
        while index1 < len(S):
            if index2 >= 0 and S[index1].isalpha() and S[index2].isalpha():
                str_ += S[index2]
                index2 -= 1
                index1 += 1
            elif S[index1].isalpha():
                index2 -= 1
            elif not S[index1].isalpha():
                str_ += S[index1]
                index1 += 1
            else:
                index2 -= 1
                index1 += 1
        return str_

ob1 = Solution()
print(ob1.reverseOnlyLetters("a-bC-dEf-ghIj"))

入力

"a-bC-dEf-ghIj"

出力

"j-Ih-gfE-dCba"

処理の流れと計算量

このアルゴリズムでは、先頭ポインタ index1 が文字列を左から右へ進みながら、末尾ポインタ index2 が右から左へ英字を探します。両者が英字同士で出会ったタイミングで値を交換するイメージです。英字以外の文字は判定された時点でそのまま出力に追加されるため、位置が保持されます。

計算量について見てみると、各文字は高々数回しか参照されないため、時間計算量は O(N)（Nは文字列の長さ）、追加のデータ構造として結果文字列が必要になるため、空間計算量も O(N) となります。

この手法は、リートコード（LeetCode）の「Reverse Only Letters（英字のみを反転）」問題などでも使われる定番テクニックなので、ぜひマスターしておきましょう。