💬 Discord
Sign In
NeetCode #922LC-6MediumMath & Geometry
← Back to All Problems

#922 · #6 · Zigzag Conversion(Z 字形变换)

📌 Problem Statement & Constraints

Given a string s and an integer numRows, write s in a zigzag pattern across numRows rows (moving down then diagonally up), then read the rows from top to bottom and concatenate them. Return the resulting string. Constraints: 1 <= s.length <= 1000, 1 <= numRows <= 1000, s consists of English letters, digits, commas and periods.

💡 Core Algorithmic Approaches

  1. Simulate the zigzag directly: append each character to the current row, then step the row index down until numRows - 1 and back up until 0.
  2. Track the current row cur and the direction step, flipping the direction whenever a boundary row is reached.
  3. Finally concatenate the rows from top to bottom.
  4. The degenerate cases numRows == 1 and numRows >= len(s) return the input unchanged, since no zigzag movement occurs.

💻 Benchmark Python3 Implementation

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        rows = [[] for _ in range(numRows)]
        cur = 0
        step = 1
        for ch in s:
            rows[cur].append(ch)
            if cur == 0:
                step = 1               # at the top: go down
            elif cur == numRows - 1:
                step = -1              # at the bottom: go up
            cur += step
        return "".join("".join(row) for row in rows)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is appended once and the final join is linear.
💾 Space Complexity
O(n): the row buffers plus the output string.

⚠️ Interview Pitfalls & Follow-ups

  • Computing positions with a period formula: direct simulation is simpler and much less error-prone.
  • Forgetting the numRows == 1 case: with a single row the direction would flip every character, and the boundary conditions degenerate.
  • Flipping the direction before appending: the character must be placed on the current row first, then the row index is advanced.
  • Concatenating into a string per row: that is quadratic in the worst case; list buffers keep it linear.