Zigzag Conversion – 6. LeetCode

The Zigzag Conversion problem is all about rearranging a string into a zigzag pattern across several rows and then reading it line by line to create a new string.

"PAYPALISHIRING" 

1. Write the string in a zig zag pattern

P   A   H   N
A P L S I I G
Y   I   R

2. Read row by row

• Row 1: PAHN
• Row 2: APLSIIG
• Row 3: YIR

3. Resulting string

"PAHNAPLSIIGYIR"

Optimal Algorithm: Row-by-Row Construction with Constant Space

• Pattern: Simulated row traversal.

• Data Structure: Use a StringBuilder array to store row strings efficiently.

This algorithm simulates how a zigzag traversal would work without actually building a 2D grid, reducing memory usage. By maintaining a direction (down or up) and row index (curRow), we directly place characters into rows. The zigzag pattern is effectively managed through these index transitions, making the solution efficient

Steps of the Algorithm:

1. Handle edge cases (e.g., numRows == 1).

2. Create numRows StringBuilder objects to represent rows.

3. Traverse the input string, appending characters to appropriate rows.

4. Track the direction (up or down) and switch it at boundaries.

5. Combine all rows into the final string.

public class ZigzagConversion {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; 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();
    }
}

Line By Line Explanation

Step 1: Handle Edge Cases

if (numRows == 1 || s.length() <= numRows) return s;

• These are cases where no zigzag conversion is required, so skip.

Step 2: Initialize Rows

StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();

• The StringBuilder for each row allows efficient character storage without repeatedly creating new strings.
• Each row will hold the characters in that specific row of the zigzag.

Step 3: Initialize Row Tracking Variables

int curRow = 0;
boolean goingDown = false;

• These variables are essential for simulating the zigzag traversal:
  • curRow determines where the next character goes.
  • goingDown changes the direction when reaching the top bottom row.

Step 4: Traverse The Input String

for (char c : s.toCharArray()) {
    rows[curRow].append(c);
    if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
    curRow += goingDown ? 1 : -1;
}

• rows[curRow].append(c): Adds the current character to the current row.
• if (curRow == 0 || curRow == numRows - 1): Checks if the current row is the first or last. If yes, switches the direction.
• curRow += goingDown ? 1 : -1; : Moves the current row pointer.
• The loop places each character in the appropriate row according to the zigzag pattern.
• Avoids unnecessary nested loops or grid structures.

Step 5: Combine All Rows

StringBuilder result = new StringBuilder();
for (StringBuilder row : rows) {
    result.append(row);
}

• Combines the characters row by row to generate the final zigzag-converted string.

Step 6: Return

return result.toString();

• Clearly separates string building (StringBuilder) from the final return value, adhering to Java’s performance best practices.

Why This Code Works

This code uses a row-wise traversal strategy with efficient string manipulation to simulate the zigzag pattern. It follows LeetCode best practices by handling edge cases early, avoiding unnecessary computations, and maintaining readability and efficiency. Each line of code serves a clear purpose in the overall solution.