Pythonで文字列を指定位置数だけシフトした後の最終的な文字列を取得するプログラム

小文字のみで構成された文字列 s と、s と同じ長さの整数リスト shifts が与えられているとします。shifts の各要素 shifts[i] は、文字列 s の先頭から i + 1 文字目までを、それぞれ shifts[i] だけシフトすることを意味します。シフトによって 'z' を超えた場合は 'a' に戻って（ラップアラウンドして）続きます。このとき、すべてのシフトを適用した後の最終的な文字列を求める必要があります。

例として、入力が s = "tomato"、shifts = [2, 5, 2, 3, 7, 4] の場合を考えてみましょう。まず先頭の1文字を2つシフトすると 't' は 'v' になり、文字列は "vomato" になります。次に先頭の2文字を5つシフトすると、文字列は "atmato" になります。この操作を順番に繰り返していき、最終的な出力は "qjcoes" となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• start に文字 "a" のASCIIコードを設定します。
• res に、文字列 s の各文字について「その文字のASCIIコード − start」を格納したリストを作成します。
• i を shifts のサイズ − 2 から 0 まで逆順にループします。
  • shifts[i] に shifts[i + 1] を加算します（後ろからの累積和を計算）。
• i を 0 から s のサイズ − 1 までループします。
  • c に (res[i] + shifts[i]) mod 26 を代入します。
  • res[i] に、ASCIIコード (c + start) に対応する文字を設定します。
• res の文字を連結して文字列にし、返します。

ポイント：後ろからの累積和

各位置 i に対する実際のシフト量は、shifts[i] 以降の要素の合計になります。そのため、リストを後ろから走査して累積和をあらかじめ求めておくことで、全体を O(n) の時間計算量で効率的に処理できます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(s, shifts):
    start = ord("a")
    res = [ord(i) - start for i in s]

    for i in range(len(shifts) - 2, -1, -1):
        shifts[i] += shifts[i + 1]

    for i in range(len(s)):
        c = (res[i] + shifts[i]) % 26
        res[i] = chr(c + start)

    return "".join(res)

s = "tomato"
shifts = [2, 5, 2, 3, 7, 4]
print(solve(s, shifts))

入力

"tomato", [2, 5, 2, 3, 7, 4]

出力

qjcoes