6. Zigzag Conversion (Medium)

Pyodide

Editor (session: default) Run

# Type here

Output Clear

Run

Editor (session: default) Run

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or len(s) <= numRows:
            return s

        rows = [''] * numRows
        current_row = 0
        going_down = False

        for char in s:
            rows[current_row] += char

            if current_row == 0 or current_row == numRows - 1:
                going_down = not going_down

            if going_down:
                current_row += 1
            else:
                current_row -= 1

        return "".join(rows)

sol = Solution()
print("--- Zigzag Conversion Examples ---")

# Test Case 1: Standard Example (numRows=3)
# P   A   H   N
# A P L S I I G
# Y   I   R
s1 = "PAYPALISHIRING"
numRows1 = 3
result1 = sol.convert(s1, numRows1)
# Expected: "PAHNAPLSIIGYIR"
print(f"Input: s='{s1}', numRows={numRows1}")
print(f"Output: '{result1}' (Expected: 'PAHNAPLSIIGYIR')")

# Test Case 2: Example with 4 rows
# P     I     N
# A   L S   I G
# Y A   H R
# P     I
s2 = "PAYPALISHIRING"
numRows2 = 4
result2 = sol.convert(s2, numRows2)
# Expected: "PINALSIGYAHRPI"
print(f"Input: s='{s2}', numRows={numRows2}")
print(f"Output: '{result2}' (Expected: 'PINALSIGYAHRPI')")
# 

# Test Case 3: Simple 2-row case
s3 = "ABCDEFGH"
numRows3 = 2
result3 = sol.convert(s3, numRows3)
# Expected: "ACEGBDFH"
print(f"Input: s='{s3}', numRows={numRows3}")
print(f"Output: '{result3}' (Expected: 'ACEGBDFH')")

# Test Case 4: numRows = 1 (Edge Case)
s4 = "ABCDE"
numRows4 = 1
result4 = sol.convert(s4, numRows4)
# Expected: "ABCDE"
print(f"Input: s='{s4}', numRows={numRows4}")
print(f"Output: '{result4}' (Expected: 'ABCDE')")

# Test Case 5: numRows >= len(s) (Edge Case)
s5 = "ABC"
numRows5 = 5
result5 = sol.convert(s5, numRows5)
# Expected: "ABC"
print(f"Input: s='{s5}', numRows={numRows5}")
print(f"Output: '{result5}' (Expected: 'ABC')")

Output Clear

Solution

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or len(s) <= numRows:
            return s

        rows = [''] * numRows
        current_row = 0
        going_down = False

        for char in s:
            rows[current_row] += char

            if current_row == 0 or current_row == numRows - 1:
                going_down = not going_down

            if going_down:
                current_row += 1
            else:
                current_row -= 1

        return "".join(rows)

Function Description

Source code in python/_6.py

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or len(s) <= numRows:
            return s

        rows = [''] * numRows
        current_row = 0
        going_down = False

        for char in s:
            rows[current_row] += char

            if current_row == 0 or current_row == numRows - 1:
                going_down = not going_down

            if going_down:
                current_row += 1
            else:
                current_row -= 1

        return "".join(rows)

convert(s, numRows)

Source code in python/_6.py

def convert(self, s: str, numRows: int) -> str:
    if numRows == 1 or len(s) <= numRows:
        return s

    rows = [''] * numRows
    current_row = 0
    going_down = False

    for char in s:
        rows[current_row] += char

        if current_row == 0 or current_row == numRows - 1:
            going_down = not going_down

        if going_down:
            current_row += 1
        else:
            current_row -= 1

    return "".join(rows)

Explanation

The problem asks you to take a given string, \(s\), and convert it into a zigzag pattern (or Z-pattern) on a specified number of rows, \(numRows\). Once the string is written in this pattern, you must read it line by line from left to right, and return the resulting new string. For example, converting "PAYPALISHIRING" with \(numRows = 3\) yields the pattern: P A H N, A P L S I I G, Y I R, which, when read row-by-row, becomes "PAHNAPLSIIGYIR".

The core of the challenge is to determine the correct row index for each character in the input string without actually creating a 2D matrix, especially since the constraints on \(s\) are up to 1000 characters. The pattern repeats in a cycle, where a full cycle covers \(numRows\) down and then \(numRows - 2\) up and diagonally. The length of one complete cycle is \(2 \times numRows - 2\). For \(numRows = 3\), the cycle length is \(2 \times 3 - 2 = 4\).

An efficient \(O(n)\) solution involves iterating through the input string \(s\) once and placing each character directly into its final row in an array of strings (or a list of StringBuilder objects). You can track the current row index and a direction flag (down or up). When the current row hits the bottom (row \(numRows - 1\)), the direction reverses to 'up'. When it hits the top (row 0), the direction reverses to 'down'. After iterating through all characters, simply concatenate the strings in the row array to produce the final zigzag-converted output.