【Python】文字列を左に回転させて全パターンを生成するプログラムの書き方

問題の概要

サイズ n の文字列 s が与えられたとき、1文字分、2文字分……n文字分と左に回転させた結果として得られる、すべての文字列を求めることを考えます。

たとえば、入力が s = "hello" の場合、出力は次のようになります。

['elloh', 'llohe', 'lohel', 'ohell', 'hello']

ご覧のとおり、先頭の文字が順番に末尾へ移動していき、n 回回転すると元の文字列「hello」に戻ります。

解き方のアプローチ

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

• 結果を格納するための空のリスト res を用意する
• 文字列 s の長さを n として取得する
• i が 0 から n-1 までの範囲でループを回す
  • s の先頭1文字を取り除き、それを末尾に付け足した新しい文字列を作成する(s[1:n] + s[0])
  • その文字列をリスト res の末尾に追加する
• 最後に res を返す

実装例

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

def solve(s):
    res = []
    n = len(s)
    for i in range(0, n):
        s = s[1:n] + s[0]
        res.append(s)
    return res

s = "hello"
print(solve(s))

入力

hello

出力

['elloh', 'llohe', 'lohel', 'ohell', 'hello']

コードのポイント

このコードの核心となるのは s[1:n] + s[0] という部分です。Pythonのスライス機能を使うことで、「先頭の1文字を除いた残りの部分」と「先頭の1文字」を連結し、左への回転をシンプルに実現しています。

各ループでの処理の流れを整理すると、次のようになります。

• 1回目:「elloh」(h が末尾へ移動)
• 2回目:「llohe」(e が末尾へ移動)
• 3回目:「lohel」(l が末尾へ移動)
• 4回目:「ohell」(o が末尾へ移動)
• 5回目:「hello」(l が末尾へ移動し、元の文字列に戻る)

文字列を n 回回転すると必ず元に戻るため、ループはちょうど n 回実行すれば十分です。計算量についても触れておくと、1回の回転に O(n)、それを n 回繰り返すため、全体の時間計算量は O(n²) となります。短い文字列であれば実用上まったく問題ありませんが、非常に長い文字列を扱う場合は注意が必要です。