Zigzag Conversion Algorithm (LeetCode 6)

The problem requires converting a given string s into a Z‑shaped arrangement based on a specified number of rows numRows , then reading the characters row‑by‑row to produce a new string.

Example: Input s = "PAYPALISHIRING" , numRows = 3 yields the Z pattern P A H N A P L S I I G Y I R and the output string "PAHNAPLSIIGYIR" .

Approach:

Create an array (or list) of strings with size numRows to store characters for each row.

Iterate over the input string, appending each character to the current row.

When the current row is the first or last row, reverse the traversal direction.

After processing all characters, concatenate the rows to obtain the final result.

Reference implementations:

C++

#include <iostream>
#include <string>
#include <vector>

std::string convert(std::string s, int numRows) {
    if (numRows == 1) return s;
    std::vector<std::string> rows(std::min(numRows, (int)s.size()));
    int curRow = 0;
    bool goingDown = false;
    for (char c : s) {
        rows[curRow] += c;
        if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
        curRow += goingDown ? 1 : -1;
    }
    std::string result;
    for (const std::string &row : rows) result += row;
    return result;
}

int main() {
    std::string s = "PAYPALISHIRING";
    int numRows = 3;
    std::cout << convert(s, numRows) << std::endl;
    return 0;
}

Java

public class Main {
    public static String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] rows = new StringBuilder[Math.min(numRows, s.length())];
        for (int i = 0; i < rows.length; i++) rows[i] = new StringBuilder();
        int curRow = 0;
        boolean goingDown = false;
        for (char c : s.toCharArray()) {
            rows[curRow].append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) result.append(row);
        return result.toString();
    }
    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        int numRows = 3;
        System.out.println(convert(s, numRows));
    }
}

Python

def convert(s: str, numRows: int) -> str:
    if numRows == 1:
        return s
    rows = [''] * min(numRows, len(s))
    cur_row = 0
    going_down = False
    for c in s:
        rows[cur_row] += c
        if cur_row == 0 or cur_row == numRows - 1:
            going_down = not going_down
        cur_row += 1 if going_down else -1
    return ''.join(rows)

# test
s = "PAYPALISHIRING"
print(convert(s, 3))