Pythonで文字列を2文字回転させて別の文字列と一致するか判定する方法

この記事では、Pythonを使って「ある文字列を左または右に2文字回転させると、もう一方の文字列と一致するかどうか」を判定する方法を解説します。

問題の概要

2つの文字列 s と t が与えられたとき、t を左方向または右方向のどちらかに2文字分回転させることで s が得られるかどうかを確認します。

例えば、入力が s = "kolkata"、t = "takolka" の場合を見てみましょう。「takolka」を左に2文字回転させると「kolkata」になるため、出力は True となります。

解決の手順

この問題は以下のステップで解決できます。

• まず、s と t の文字数が異なる場合は、回転しても一致することはないため False を返します。
• 右回転用の結果を格納するための空文字列 right_rot を用意します。
• 同様に、左回転用の空文字列 left_rot を用意します。
• 変数 l に t の長さを代入します。
• 左回転の場合：t の末尾2文字（インデックス l-2 以降）を先頭に移動し、残りの部分（インデックス 0 から l-3 まで）を後ろに連結します。
• 右回転の場合：t の先頭2文字を除いた部分（インデックス 2 以降）を前にし、先頭2文字（インデックス 0 から 1 まで）を末尾に連結します。
• 最後に、s が right_rot または left_rot のいずれかと一致すれば True、そうでなければ False を返します。

実装例

それでは、実際のコードを見て理解を深めましょう。

def solve(s, t):
    if (len(s) != len(t)):
        return False
    right_rot = ""
    left_rot = ""
    l = len(t)
    left_rot = (left_rot + t[l - 2:] + t[0: l - 2])
    right_rot = right_rot + t[2:] + t[0:2]
    return (s == right_rot or s == left_rot)

s = "kolkata"
t = "takolka"
print(solve(s, t))

入力

"kolkata", "takolka"

出力

True

コードの解説

このアルゴリズムのポイントは、Pythonのスライス記法を活用している点です。t[l-2:] は文字列の末尾2文字を取得し、t[0:l-2] は先頭から末尾2文字を除いた部分を取得します。これらを連結することで、左への2文字回転を実現しています。同様に、t[2:] と t[0:2] を連結することで右への2文字回転を作成しています。

計算量は文字列の長さを n とすると O(n) となり、非常に効率的です。文字列の長さチェックを最初に行うことで、長さが異なるケースを素早く除外できる点も実用的です。