What is the simplest way to implement Zigzag Conversion for interviews?

Use row-wise simulation with an array of strings and direction flags, then concatenate all rows at the end.

How do I handle numRows greater than the string length?

Return the string directly or treat each character as a separate row since the zigzag pattern collapses.

Can this approach work for very long strings efficiently?

Yes, both row-wise simulation and index calculation operate in O(n) time and O(n) space, scaling linearly with string length.

Is it necessary to use extra arrays for rows?

Not strictly; you can compute character positions with cycle-based index formulas to avoid additional arrays.

How does the string-driven solution strategy apply to Zigzag Conversion?

It focuses on iterating characters in sequence while tracking their target row, aligning perfectly with the zigzag reading requirement.

#6

Medium

auto_awesomeString-driven solution strategy

LeetCode 题解工作台

Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下： P A H N A P L S I I G Y I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如： …

字符串

题目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

lightbulb

解题思路

方法一：模拟

我们用一个二维数组 $g$ 来模拟 Z 字形排列的过程，其中 $g[i][j]$ 表示第 $i$ 行第 $j$ 列的字符。初始时 $i = 0$ ，另外我们定义一个方向变量 $k$ ，初始时 $k = -1$ ，表示向上走。

我们从左到右遍历字符串 $s$ ，每次遍历到一个字符 $c$ ，将其追加到 $g[i]$ 中。如果此时 $i = 0$ 或者 $i = \textit{numRows} - 1$ ，说明当前字符位于 Z 字形排列的拐点，我们将 $k$ 的值反转，即 $k = -k$ 。接下来，我们将 $i$ 的值更新为 $i + k$ ，即向上或向下移动一行。继续遍历下一个字符，直到遍历完字符串 $s$ ，我们返回 $g$ 中所有行拼接后的字符串即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        g = [[] for _ in range(numRows)]
        i, k = 0, -1
        for c in s:
            g[i].append(c)
            if i == 0 or i == numRows - 1:
                k = -k
            i += k
        return ''.join(chain(*g))

speed

复杂度分析

指标	值
时间	complexity is O(n) since each character is processed once, either by appending to row strings or calculating indices. Space complexity is O(n) for storing characters per row and the final concatenated result, matching the input size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for off-by-one errors in row traversal during zigzag simulation.
question_mark
Check whether candidate handles single-row or short strings correctly.
question_mark
Listen for explanations about string indexing versus direct row concatenation for pattern efficiency.

warning

常见陷阱

外企场景

error
Forgetting to reverse direction when reaching top or bottom row, breaking the zigzag pattern.
error
Preallocating insufficient row arrays, causing index errors for large numRows values.
error
Confusing cycle calculation indices, leading to incorrect concatenation order.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Convert a string with custom row patterns like alternating multiple zigzags per cycle.
arrow_right_alt
Implement zigzag reading in a memory-efficient way using a single string buffer and offsets.
arrow_right_alt
Support dynamic row counts determined at runtime, requiring adaptable indexing or row arrays.

help

常见问题

外企场景

继续练习

#5 最长回文子串 #8 字符串转换整数 (atoi)#3 无重复字符的最长子串