【C++】文字列をジグザグ変換するアルゴリズムと実装例

ジグザグ変換とは？

文字列「IWANTTOLEARNCODE」を、指定された行数（n 行）に対してジグザグ状に配置することを考えてみましょう。3 行の場合、パターンは次のようになります。

この配置を行ごとに上から順に読み上げると、「ITECWNTLANOEAORD」という文字列が得られます。

つまり今回は、元の文字列と行数を受け取り、この変換処理を実行するモジュール（関数）を作成することが目標となります。

解法のステップ

この問題は、次の手順に従って解くことができます。

1. n = 1 の場合は、変換の必要がないためそのまま s を返します。
2. サイズ n の文字列配列 arr を用意します。
3. 現在の行を表す row := 0 と、進行方向を表す down := true で初期化します。
4. i を 0 から文字列の長さ - 1 までループさせます。
   • s[i] を arr[row] の末尾に追加します。
   • row が b - 1（最終行）に達したら down := false に、row が 0（先頭行）に戻ったら down := true に切り替えます。
   • down が true なら row を 1 増やし、false なら 1 減らします。
5. 答えを格納するための空文字列 ans を用意します。
6. i を 0 から n - 1 までループし、ans に arr[i] を順番に連結していきます。
7. ans を返します。

C++による実装例

それでは、以下の実装を見ながら理解を深めていきましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string convert(string s, int numRows);
};
string Solution::convert(string a, int b) {
    if(b == 1)return a;
    string arr[b];
    int row = 0;
    bool down = true;
    for(int i = 0; i < a.size(); i++){
        arr[row].push_back(a[i]);
        if(row == b - 1) down = false;
        else if(row == 0)down = true;
        if(down) row++;
        else row--;
    }
    string ans = "";
    for(int i = 0; i < b; i++){
        ans += arr[i];
    }
    return ans;
}
main(){
    Solution ob;
    cout << ob.convert("IWANTTOLEARNCODE", 3);
}

入力

"IWANTTOLEARNCODE"
3

出力

"ITECWNTLANOEAORD"

仕組みのポイント

このアルゴリズムでは、文字を 1 文字ずつ処理しながら、行番号を「下へ降りては上へ戻る」往復運動させることで、ジグザグの配置を再現しています。あとは行ごとに振り分けられた文字列を先頭行から順に連結するだけで、目的の結果が得られます。計算量は文字列の長さに対して線形時間 O(n) となり、非常に効率的な手法です。