60. ZigZag Conversion

読了目安約2分

その他 / LeetCode 6 (Medium) — 文字列をジグザグに並べて行順に読み直す

この章の目次

問題

LeetCode 6. ZigZag Conversion（Medium / カテゴリ: その他）

文字列 s を numRows 行のジグザグに並べ替える問題です。文字を上の行から下の行へ 1 文字ずつ置き、最下行に着いたら斜め上に戻る、を繰り返します。並べ終えたら、上の行から順に左から右へ読んだ文字列を返します。

例: "PAYPALISHIRING" を 3 行に並べると次の形になり、行順に読むと "PAHNAPLSIIGYIR" です。

テキスト
P   A   H   N
A P L S I I G
Y   I   R

考え方

ヒント 1

2 次元の盤面を作る必要はありません。各文字が何行目に置かれるかだけ分かれば、答えは組み立てられます。

ヒント 2

現在の行 row と進行方向 step (+1 か -1) を持ちます。文字を rows[row] に追加し、最上行なら step = 1、最下行なら step = -1 に切り替えてから row += step します。最後に rows を連結すれば答えです。

Swift 実装のポイント

行ごとの文字列は Array(repeating: "", count: numRows) で用意し、最後に joined() で連結します。
numRows == 1 は方向転換が起きず row が範囲外へ進むので、s をそのまま返す特別扱いにします。
方向の切り替えは「文字を追加した後、row を進める前」に行います。順序を誤ると端で範囲外アクセスになります。

模範解答

Swift
class Solution {
    func convert(_ s: String, _ numRows: Int) -> String {
        if numRows == 1 {
            return s
        }
        var rows = Array(repeating: "", count: numRows)
        var row = 0
        var step = 1
        for ch in s {
            rows[row].append(ch)
            if row == 0 {
                step = 1
            } else if row == numRows - 1 {
                step = -1
            }
            row += step
        }
        return rows.joined()
    }
}

計算量: O(n)。

これで Arai60 完走です。復習は Arai60 の進め方に従って 3 周を目指してください。