Pythonで2つの文字列が回転関係にあるかどうかを判定する方法

問題概要

2つの文字列 s と t が与えられたとき、t が s を回転（ローテーション）させたものになっているかどうかを判定します。

例えば、s = "hello"、t = "llohe" の場合、s を左に2文字分回転すると "llohe" になるため、結果は True となります。

解法のアプローチ

この問題は「文字列を自分自身と連結する」というシンプルなテクニックで効率的に解くことができます。手順は以下の通りです。

• s と t の長さが異なる場合、回転関係にはなり得ないので False を返します。
• temp := s + s として、s を2回連結した文字列を作成します。
• temp の中に t が含まれている（出現回数が0より大きい）場合は True を返します。
• それ以外の場合は False を返します。

この手法が機能する理由は、s を2回連結した文字列には、s のすべての回転パターンが必ず部分文字列として含まれるためです。

サンプルコード

def solve(s, t):
    if len(s) != len(t):
        return False

    temp = s + s

    if temp.count(t) > 0:
        return True
    return False

s = "hello"
t = "llohe"
print(solve(s, t))

入力

"hello", "llohe"

出力

True

補足：in演算子を使ったより簡潔な書き方

count() メソッドの代わりに in 演算子を使うと、コードをさらに簡潔にできます。

def solve(s, t):
    return len(s) == len(t) and t in s + s

この1行版では、まず長さが等しいことを確認し、その上で t が s + s に含まれるかどうかを一度に判定しています。計算量は O(n) で、文字列比較も高速に行えます。