C++でn行のジグザグ文字列の連結を出力する方法

この問題では、文字列が与えられ、ジグザグパターンの行数nも指定されます。そして、その文字列をn行のジグザグパターンに配置したとき、各行の文字を読み取って連結した結果を出力する必要があります。

具体例を見ながら、この概念をより深く理解していきましょう。

例1

入力 : 文字列 = 'STUVWXYZ'、 n = 2
出力 : SUWYTVXZ

解説 − この文字列を2行のジグザグパターンに配置すると、以下のようになります。

S     U     W     Y
   T     V     X     Z

このジグザグパターンを行ごとに連結すると、「SUWYTVXZ」となります。上の行（S, U, W, Y）と下の行（T, V, X, Z）を順番につなげたものです。

例2

入力 : 文字列 = 'ABCDEFGH'、 n = 3
出力 : AEBDFHCG

解説 − 3行のジグザグパターンの場合、次のように配置されます。

A       E
  B   D   F   H
    C       G

各行を連結すると、AEBDFHCG が出力結果となります。

解法のアプローチ

問題の内容が把握できたところで、解法を設計していきましょう。基本的な考え方は、文字列を先頭から順に走査しながら、現在の行位置を管理することです。行が一番下（n-1行目）に達するまで下方向へ進み、そこに到達したら今度は上方向へ進みます。行が一番上（0行目）に戻ったら、再び下方向へ進む、という動作を繰り返します。

各文字は、その時点の行に対応する文字列バッファに追加していき、最後にすべての行を上から順に出力すれば完成です。

アルゴリズム

ステップ1 : サイズnの文字列配列 arr[n]、現在の行番号 row、方向 direction = 1（下向き移動を表す）を用意します。
ステップ2 : 文字列を走査し、各文字に対してステップ3〜7を実行します。
ステップ3 : 現在の row の値に基づいて、対応する配列内の文字列に文字を追加します。
ステップ4 : もし row == n-1 なら、direction = -1 に設定します（上向きへ切り替え）。
ステップ5 : もし row == 0 なら、direction = 1 に設定します（下向きへ切り替え）。
ステップ6 : direction == 1 なら、row をインクリメントします。
ステップ7 : それ以外なら、row をデクリメントします。
ステップ8 : 配列内のすべての文字列を、0からn-1まで順番に出力します。

C++での実装例

このアルゴリズムをもとに、実際のプログラムを作成してみましょう。

#include<bits/stdc++.h>
using namespace std;

void ZigZagConcatenationString(string str, int n){
    // 行数が1の場合はジグザグにならないため、そのまま出力
    if (n == 1){
        cout << str;
        return;
    }
    int len = str.length();
    string arr[n];
    int row = 0;
    int direction = 1;
    for (int i = 0; i < len; ++i){
        // 現在の行に文字を追加
        arr[row].push_back(str[i]);
        // 最下行に到達したら方向を上向きに変更
        if (row == n-1)
            direction = -1;
        // 最上行に到達したら方向を下向きに変更
        else if (row == 0)
            direction = 1;
        // 方向に応じて行を移動
        (direction == 1)? (row++): (row--);
    }
    // 各行の文字列を順番に出力
    for (int i = 0; i < n; ++i)
        cout << arr[i];
}

int main(){
    string str = "ABCDEFGH";
    int n = 3;
    ZigZagConcatenationString(str, n);
    return 0;
}

実行結果

AEBDFHCG

計算量について

このアルゴリズムの時間計算量は O(n) です。ここでnは文字列の長さを表し、文字列全体を一度だけ走査すればよいため効率的です。空間計算量も O(n) となり、各行ごとの文字列を格納するために追加のメモリが必要になります。

このように、行の移動方向を管理しながら文字を振り分けていくシンプルな手法で、ジグザグパターンの文字列連結問題を効率的に解くことができます。