LeetCode: 6. Zigzag Conversion

LeetCode: 6. Zigzag Conversion

Summary

Convert a string written in a zigzag pattern into the row-by-row reading order.

numRows controls the zigzag shape.

Approach

Find the correct row index for each character. Then build the final string from the per-row characters.

Function

Initialization:

• current_row = 0
• zigzag_mode = 1 (1 means go down, -1 means go up)
• row_patterns = [[] for _ in range(numRows)]

Main loop:

For each character ch in s:

• Add ch to row_patterns[current_row].
• Move to the next row: current_row += zigzag_mode.
• Update direction when needed: if current_row == 0 or current_row == numRows - 1, then zigzag_mode *= -1.

Convert row patterns to a string:

• Join each row.
• Join all rows together.

Complexity

Time Complexity: O(N). We traverse each character once, and joining rows is also O(N). Space Complexity: O(N) for storing row patterns.