🐇
JavaScriptで解く！『LeetCode Arai 60』#5 Zigzag Conversion

2024/12/27に公開
 JavaScriptで解く！『LeetCode Arai 60』#5 Zigzag Conversion「Zigzag Conversion」は、文字列をジグザグ（上下に行ったり来たり）に並べ替える問題です。

この問題を解くポイントはどうやってジグザグに文字を配置するかというところ。

ここでは、2次元配列を使った解法を取り上げます。

 1. 問題のイメージ例えば、文字列 "PAYPALISHIRING" を行数3でジグザグに並べると：
P   A   H   N
A P L S I I G
Y   I   R
これを1行で読み取ると、"PAHNAPLSIIGYIR" という文字列になります。

 2. どうやって解くの？行ごとの配列を作成する
まずは行の数だけ配列を用意します。（例：3行なら [ [], [], [] ] という形）
ジグザグに文字を配置する
上から下に進むときと、下から上に戻るときで行番号を変化させながら、文字を順番に配置していきます。
最終的に行ごとの配列を1つにまとめる
各行に入っている文字配列をすべて結合して、最終的な文字列を作ります。

 3. 4行の場合の初期配列イメージもし行数が4なら、初期状態の配列は次のようになります。
[
  [],
  [],
  [],
  []
]
この4つの配列（行）に対して、文字を上下に移動させながら配置していくわけです。

（※実際のサンプルでは行数3で解説していますが、行数4の場合も同様にこのような2次元配列が必要になります。）

 4. 例： "helloworld" を行数3でジグザグに配置するステップここでは、文字列 "helloworld" を行数3で配置する具体的な流れを見てみましょう。

はじめに、3行分の空配列を用意します。
[
  [], // 1行目
  [], // 2行目
  []  // 3行目
]

 ステップごとの配置Step 1 (i=0)
文字：'h'
現在の行：1行目に配置（初期状態は row=1, headingDown=true）
配列： [ ['h'], [], [] ]
次に row++ → row=2
Step 2 (i=1)
文字：'e'
現在の行：2行目
配列： [ ['h'], ['e'], [] ]
次に row++ → row=3
Step 3 (i=2)
文字：'l'
現在の行：3行目
配列： [ ['h'], ['e'], ['l'] ]
次に row++ → 4行目に行こうとする → row > targetRows(3) なので

row = targetRows - 1 = 2 に戻す

headingDown = false（上向きに切り替え）

Step 4 (i=3)
文字：'l'
現在の行：2行目（上向き）
配列： [ ['h'], ['e', 'l'], ['l'] ]
次に row-- → row=1
Step 5 (i=4)
文字：'o'
現在の行：1行目
配列： [ ['h', 'o'], ['e', 'l'], ['l'] ]
次に row-- → row=0 → row < 1 なので

row = 2 に戻す

headingDown = true（下向きに切り替え）

Step 6 (i=5)
文字：'w'
現在の行：2行目（下向き）
配列： [ ['h', 'o'], ['e', 'l', 'w'], ['l'] ]
次に row++ → row=3
Step 7 (i=6)
文字：'o'
現在の行：3行目
配列： [ ['h', 'o'], ['e', 'l', 'w'], ['l', 'o'] ]
次に row++ → row=4 → row > 3 なので

row = 2 に戻す

headingDown = false（上向きに切り替え）

Step 8 (i=7)
文字：'r'
現在の行：2行目（上向き）
配列： [ ['h', 'o'], ['e', 'l', 'w', 'r'], ['l', 'o'] ]
次に row-- → row=1
Step 9 (i=8)
文字：'l'
現在の行：1行目
配列： [ ['h', 'o', 'l'], ['e', 'l', 'w', 'r'], ['l', 'o'] ]
次に row-- → row=0 → row < 1 なので
row = 2
headingDown = true

Step 10 (i=9)
文字：'d'
現在の行：2行目（下向き）
配列： [ ['h', 'o', 'l'], ['e', 'l', 'w', 'r', 'd'], ['l', 'o'] ]
次に row++ → row=3 → ちょうど最大行数なのでOK
最終的な2次元配列は下記のとおり。
[
  ['h', 'o', 'l'],        // 1行目
  ['e', 'l', 'w', 'r', 'd'], // 2行目
  ['l', 'o']             // 3行目
]

 文字列を一つにまとめる最後に、各行の配列を結合します。
1行目: "hol"
2行目: "elwrd"
3行目: "lo"
結果: hol + elwrd + lo = "holelwrdlo"

 5. コード全体var convert = function (inputString, targetRows) {
    // 目標の行数が1の場合は、そもそもジグザグにならないのでそのまま返す
    if (targetRows === 1) {
        return inputString;
    }

    // 現在の行を表す変数。最初は1行目からスタート
    let currentRow = 1;
    // 下向きに進んでいるかを示すフラグ
    let headingDown = true;

    // 2次元配列を用意（例：3行なら [[], [], []] ）
    let zigZagArray = [];
    for (let i = 0; i < targetRows; i++) {
        zigZagArray[i] = [];
    }

    // 文字列を1文字ずつ、ジグザグ配置
    for (let i = 0; i < inputString.length; i++) {
        // currentRow - 1 のインデックスに文字を追加
        zigZagArray[currentRow - 1].push(inputString[i]);

        if (headingDown) {
            // 下向き
            currentRow++;
            // 最下行を超えた場合、方向を上向きに変更
            if (currentRow > targetRows) {
                currentRow = targetRows - 1;
                headingDown = false;
            }
        } else {
            // 上向き
            currentRow--;
            // 最上行を超えた場合、方向を下向きに変更
            if (currentRow < 1) {
                currentRow = 2;
                headingDown = true;
            }
        }
    }

    // 行ごとの文字配列を結合して1つの文字列に
    let totalString = '';
    for (let i = 0; i < targetRows; i++) {
        totalString += zigZagArray[i].join('');
    }

    return totalString;
};

 6. コードのポイント解説ジグザグを「行を上下に移動するフラグ」で管理

headingDown が true なら currentRow++ して下へ

false なら currentRow-- して上へ
最下行や最上行を超えてしまったら、進行方向を反転

currentRow > targetRows のときに最下行を超えた → 上向きへ切り替え

currentRow < 1 のときに最上行を超えた → 下向きへ切り替え
2次元配列で各行の文字を管理して、一気に結合

zigZagArray[row] に1文字ずつ追加
最後に zigZagArray[i].join('') して1つの文字列にまとめる

 7. まとめ
2次元配列を使うことで、どの行にどの文字がいるかを簡単に管理できます。
行の移動を「下に行くか」「上に戻るか」というフラグで切り替えるのがポイント。
最終的に各行を結合するだけなので、ロジックがシンプルになり、バグも減らせます。
このアルゴリズムをしっかり理解すれば、他の文字列操作問題にも応用可能です。ぜひ試してみてください！
JavaScriptで解く！『LeetCode Arai 60』#5 Zigzag Conversion

JavaScriptで解く！『LeetCode Arai 60』#5 Zigzag Conversion

1. 問題のイメージ

2. どうやって解くの？

3. 4行の場合の初期配列イメージ

4. 例： `"helloworld"` を行数3でジグザグに配置するステップ

ステップごとの配置

文字列を一つにまとめる

5. コード全体

6. コードのポイント解説

7. まとめ

Discussion
