【Python入門】2つの文字列が互いの回転かどうかを判定する方法

この記事では、2つの英文字列 s と t（大文字・小文字が混在していても可）が与えられたとき、一方がもう一方の回転であるかどうかを判定するプログラムを Python で実装する方法を解説します。

回転とは？

文字列の「回転」とは、文字列の先頭からいくつかの文字を取り除き、それを末尾に移動させる操作によって得られる文字列のことです。例えば、s = "koLKAta" と t = "KAtakoL" が与えられた場合、t は s を回転させた結果と一致するため、出力は True になります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 長さの確認： s と t の長さが異なる場合は、回転になり得ないため False を返します。
• 文字列の連結： s を自分自身と連結します（s = s + s）。回転した文字列は必ずこの連結後の文字列の中に部分文字列として現れます。
• 存在確認： 連結後の文字列の中に t が含まれていれば True、含まれていなければ False を返します。

実装例

以下が実際の Python コードです。

def solve(s, t):
    if len(s) != len(t):
        return False
    s = s + s
    return True if s.find(t) != -1 else False

s = "koLKAta"
t = "KAtakoL"
print(solve(s, t))

コードのポイント

s.find(t) は、t が見つかった場合はその開始インデックスを、見つからなかった場合は -1 を返します。この性質を利用して、回転判定を行っています。なお、Python の in 演算子を使って return t in s と書くことで、より簡潔に記述することも可能です。

入力例

s = "koLKAta", t = "KAtakoL"

出力例

True

計算量について

このアルゴリズムの時間計算量は O(n) です（n は文字列の長さ）。部分文字列検索には効率的なアルゴリズムが使われるため、大きな文字列でも高速に動作します。空間計算量も O(n) で、連結後の文字列を保存するために必要となります。