Pythonで文字列をk行のジグザグパターンに変換するプログラムを解説

文字列 s と整数 k が与えられたとき、s の各文字を順に取り出し、左上から右下へ斜めに進んで k 行目に達したら、今度は右上へ折り返す――この動きを繰り返してできる「ジグザグ型」の文字列を作成する方法を解説します。

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

解法のアプローチ

この問題は、いわゆる「蛇行（ジグザグ）パターン」への文字列変換です。各行にどの文字がどの位置に来るかを記録しておき、最後に行単位で組み立てるのがポイントです。具体的には、次の手順で解きます。

• 初期化：各行の文字情報を格納する辞書 line を用意し、現在の行番号 cnt を 0、移動方向 delta を 1（下向き）に設定します。
• 文字の割り当て：文字列 s の各インデックス i と文字 c について、ペア (c, i) を line[cnt] の末尾に追加します。
• 方向の反転：cnt に delta を加算しながら進み、cnt が k に達したら方向を反転（delta = -1）して cnt を k - 2 に戻します。逆に cnt が 0 になったら、再び下向き（delta = 1）に切り替えます。
• 結果の組み立て：辞書 line の各行について、元の文字列と同じ長さの空白文字リスト prefix を作成し、記録しておいた位置 y に文字 x を埋め込みます。その後、リストの要素を連結して 1 行分の文字列にし、ans に追加します。
• 出力：ans の各行を改行文字で連結した文字列を返します。

理解を深めるために、以下の実装例を見てみましょう。

実装例

from collections import defaultdict

class Solution:
    def solve(self, s, k):
        line = defaultdict(list)
        cnt = 0
        delta = 1
        for i, c in enumerate(s):
            line[cnt].append((c, i))
            cnt += delta
            if cnt == k:
                delta = -1
                cnt = k - 2
            if cnt == 0:
                delta = 1

        ans = []

        for i, c in line.items():
            prefix = [" "] * (len(s))
            for x, y in c:
                prefix[y] = x
            ans.append("".join(prefix))

        return "\n".join(ans)

ob = Solution()
s = "ilovepythonprogramming"
k = 5
print(ob.solve(s, k))

入力

"ilovepythonprogramming", 5

出力

計算量の目安

文字列の長さを n とすると、各文字を一度ずつ処理するため時間計算量は O(n) です。一方、行ごとの結果を保持するために O(n × k) のメモリを使用します。k が極端に大きくない限り、十分に高速に動作するシンプルで効率的なアルゴリズムです。