ZigZag Conversion

medium string simulation

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows);

Inputs = "PAYPALISHIRING", numRows = 3

Output"PAHNAPLSIIGYIR"

Row 0: P A H N. Row 1: A P L S I I G. Row 2: Y I R.

numRows

def convert(s, num_rows):
    if num_rows == 1:
        return s
    rows = [""] * num_rows
    r, d = 0, 1
    for ch in s:
        rows[r] += ch
        if r == 0:
            d = 1
        elif r == num_rows - 1:
            d = -1
        r += d
    return "".join(rows)

function convert(s, numRows) {
  if (numRows === 1) return s;
  const rows = Array.from({ length: numRows }, () => "");
  let r = 0, dir = 1;
  for (const ch of s) {
    rows[r] += ch;
    if (r === 0) dir = 1;
    else if (r === numRows - 1) dir = -1;
    r += dir;
  }
  return rows.join("");
}

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        int r = 0, dir = 1;
        for (char ch : s.toCharArray()) {
            rows[r].append(ch);
            if (r == 0) dir = 1;
            else if (r == numRows - 1) dir = -1;
            r += dir;
        }
        StringBuilder out = new StringBuilder();
        for (StringBuilder row : rows) out.append(row);
        return out.toString();
    }
}

string convert(string s, int numRows) {
    if (numRows == 1) return s;
    vector<string> rows(numRows);
    int r = 0, dir = 1;
    for (char ch : s) {
        rows[r] += ch;
        if (r == 0) dir = 1;
        else if (r == numRows - 1) dir = -1;
        r += dir;
    }
    string out;
    for (auto& row : rows) out += row;
    return out;
}

Explanation

Instead of literally drawing the zigzag grid, we just track which row each character lands on and append it to that row's bucket. At the end we glue all the rows together.

We keep one string per row. A pointer r says which row we're on, and a direction d says whether we're heading down or up. As we read the string character by character, we drop each character into rows[r].

The zigzag motion is just a bounce: when r hits the top row (0) we set direction to down (+1); when it hits the bottom row (numRows - 1) we set it to up (-1). Then r += d moves us one step.

Example with "PAYPALISHIRING" and 3 rows: P goes to row 0, A to row 1, Y to row 2 (now bounce up), P to row 1, A to row 0 (bounce down), and so on. Row 0 collects PAHN, row 1 APLSIIG, row 2 YIR.

Joining the rows top to bottom gives "PAHNAPLSIIGYIR". The early numRows == 1 check just avoids dividing the string when there is no zigzag at all.

Time: O(n) Space: O(n)