【Python】文字列の連結ルールに従って数列のn番目の項を求めるプログラム

問題の概要

2つの文字列 s、t と正の整数 n が与えられたとします。このとき、次のルールで定義される数列 A の第 n 項を求める必要があります。

• A[0] = s
• A[1] = t
• n が偶数のとき：A[n] = A[n-1] + A[n-2]
• n が奇数のとき：A[n] = A[n-2] + A[n-1]

ここで「+」は文字列の連結を表します。ポイントは、添字の偶奇によって連結する順序が入れ替わる点です。

具体例

s = "a"、t = "b" の場合、数列 A は次のように生成されます。

• A[0] = "a"
• A[1] = "b"
• A[2] = "ba"（"b" + "a"）
• A[3] = "bba"（"b" + "ba"）
• A[4] = "bbaba"（"bba" + "ba"）

同様に、入力が s = "pk"、t = "r"、n = 4 の場合、出力は "rrpkrpk" となります。

解き方のアプローチ

この問題は、フィボナッチ数列と同じ要領で前の2項を使いながら反復的に計算すれば解けます。手順は以下の通りです。

1. n が 0 の場合は s をそのまま返す。
2. n が 1 の場合は t をそのまま返す。
3. a = s、b = t として初期化する。
4. i を 2 から n まで順に処理する。
   • i が偶数なら c = b + a（連結）
   • i が奇数なら c = a + b（連結）
   • その後、a = b、b = c と更新する。
5. 最終的に c を返す。

Pythonでの実装例

class Solution:
    def solve(self, s, t, n):
        if n == 0:
            return s
        elif n == 1:
            return t
        a = s
        b = t
        for i in range(2, n + 1):
            if i % 2 == 0:
                c = b + a
            else:
                c = a + b
            a = b
            b = c
        return c

ob = Solution()
print(ob.solve("pk", "r", 4))

入力

"pk", "r", 4

出力

rrpkrpk

計算量について

ループは n 回しか回らないため、反復回数ベースでは O(n) です。ただし、各項の文字列長はフィボナッチ数列のように増加していくため、n が大きくなると生成される文字列自体のサイズが指数的に膨らむ点には注意が必要です。メモリ使用量も文字列長に比例して増えるため、実用上は n の上限を考慮して設計しましょう。