Zigzag Conversion

アルゴリズム概要

文字列を指定された行数のジグザグパターンで配置し、各行を左から右へ読み出して連結した文字列を返す問題です。

問題例

P   A   H   N
A P L S I I G
Y   I   R
      

制約

• 1 ≤ s.length ≤ 1000
• s は英字（大文字小文字）、カンマ、ピリオドで構成
• 1 ≤ numRows ≤ 1000

戦略

• 周期式の発見: ジグザグの周期は cycle = 2 * (numRows - 1)
• 行別走査: 各行について、縦成分と斜め成分（中間行のみ）を直接計算
• 端行の特殊処理: 0行目と最終行は斜め成分なし
• 効率的なメモリ使用: 固定長リストに逐次代入し、最後に結合

主要ポイント

ステップバイステップ解説

Python実装

from __future__ import annotations
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    pass


class Solution:
    """
    LeetCode 6. Zigzag Conversion
    - 競技向け: convert() は高速版を直接呼び出し
    - 実務向け: 必要に応じて _validate_inputs() を有効化
    """

    def convert(self, s: str, numRows: int) -> str:
        """
        文字列を numRows 行のジグザグ配置で並べ替え、行ごとに読み出す。

        Args:
            s: 変換対象の文字列（長さ 1..1000）
            numRows: 行数（1..1000）

        Returns:
            変換後の文字列

        Time: O(n), Space: O(1) (出力バッファ除く)
        """
        n: int = len(s)

        # 基底条件: ジグザグ不要
        if numRows == 1 or numRows >= n:
            return s

        # 周期: ジグザグの1サイクル = 2*(numRows-1)
        cycle: int = (numRows - 1) * 2
        out: list[str] = [""] * n
        k: int = 0  # 出力リストの書き込み位置

        # ローカル束縛で属性アクセスを削減
        _s = s
        _n = n
        _out = out
        _cycle = cycle
        last_row = numRows - 1

        for row in range(numRows):
            i = row  # 現在行の縦成分の開始インデックス

            if row == 0 or row == last_row:
                # 端行: 斜め成分なし、周期刻みで縦成分のみ
                while i < _n:
                    _out[k] = _s[i]
                    k += 1
                    i += _cycle
            else:
                # 中間行: 縦成分 + 斜め成分
                step_diag = _cycle - (row << 1)  # cycle - 2*row
                while i < _n:
                    # 縦成分
                    _out[k] = _s[i]
                    k += 1
                    # 斜め成分（範囲内なら追加）
                    diag_idx = i + step_diag
                    if diag_idx < _n:
                        _out[k] = _s[diag_idx]
                        k += 1
                    i += _cycle

        return "".join(_out)

フローチャート

フローの説明：
1. 基底条件: numRows が 1 または n 以上の場合、ジグザグ不要なので元の文字列を返却
2. 周期計算: cycle = 2*(numRows-1) でジグザグの周期を計算
3. 行別走査: 各行について、端行（0行目、最終行）は縦成分のみ、中間行は縦+斜め成分を追加
4. 結合: 出力リストを文字列に結合して返却

計算量分析

代替手法との比較