LeetCode 6: Zigzag Conversion (Row Simulation)
LeetCode 6StringSimulationInterviewToday we solve LeetCode 6 - Zigzag Conversion.
Source: https://leetcode.com/problems/zigzag-conversion/
English
Problem Summary
Given a string s and an integer numRows, write the characters in a zigzag pattern across rows, then read row by row to form a new string.
Key Insight
You do not need a 2D matrix. Just simulate writing characters into row buffers, moving row index downward then upward repeatedly.
Brute Force and Limitations
A matrix-style simulation stores many empty slots and has awkward indexing. It wastes memory and makes reconstruction clumsy.
Optimal Algorithm Steps
1) If numRows == 1 or numRows >= s.length(), return s.
2) Prepare numRows string builders.
3) Track row and direction step (+1 down, -1 up).
4) Append each character to current row, then move row by step.
5) Flip direction at top row (0) and bottom row (numRows-1).
6) Concatenate all row buffers.
Complexity Analysis
Time: O(n), each character is appended once.
Space: O(n), output buffers store all characters.
Common Pitfalls
- Forgetting edge case numRows == 1.
- Flipping direction at wrong time (before appending / after moving).
- Using costly string concatenation inside loop instead of row buffers.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) return s;
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
int row = 0;
int step = 1;
for (char ch : s.toCharArray()) {
rows[row].append(ch);
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
StringBuilder ans = new StringBuilder();
for (StringBuilder sb : rows) ans.append(sb);
return ans.toString();
}
}func convert(s string, numRows int) string {
n := len(s)
if numRows == 1 || numRows >= n {
return s
}
rows := make([][]byte, numRows)
row, step := 0, 1
for i := 0; i < n; i++ {
rows[row] = append(rows[row], s[i])
if row == 0 {
step = 1
} else if row == numRows-1 {
step = -1
}
row += step
}
ans := make([]byte, 0, n)
for _, r := range rows {
ans = append(ans, r...)
}
return string(ans)
}class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1 || numRows >= (int)s.size()) return s;
vector<string> rows(numRows);
int row = 0, step = 1;
for (char ch : s) {
rows[row].push_back(ch);
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
string ans;
for (auto& r : rows) ans += r;
return ans;
}
};class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
rows = ["" for _ in range(numRows)]
row, step = 0, 1
for ch in s:
rows[row] += ch
if row == 0:
step = 1
elif row == numRows - 1:
step = -1
row += step
return "".join(rows)var convert = function(s, numRows) {
if (numRows === 1 || numRows >= s.length) return s;
const rows = Array.from({ length: numRows }, () => []);
let row = 0;
let step = 1;
for (const ch of s) {
rows[row].push(ch);
if (row === 0) step = 1;
else if (row === numRows - 1) step = -1;
row += step;
}
return rows.map(r => r.join('')).join('');
};中文
题目概述
给定字符串 s 和行数 numRows，按 Z 字形把字符写入多行，最后按行拼接得到转换结果。
核心思路
不需要真实二维矩阵。只要维护每一行的字符串缓冲，并用行号在“向下/向上”之间来回移动即可。
暴力解法与不足
若用矩阵硬模拟，会产生大量空位、索引复杂，空间浪费也明显。
最优算法步骤
1）当 numRows == 1 或 numRows >= s.length() 时直接返回原串。
2）准备 numRows 个行缓冲。
3）维护当前行 row 与方向 step（向下 +1，向上 -1）。
4）每读一个字符，追加到当前行，然后按方向移动。
5）到达顶行或底行时反转方向。
6）最后按行顺序拼接所有缓冲。
复杂度分析
时间复杂度：O(n)，每个字符只处理一次。
空间复杂度：O(n)，行缓冲总共存放全部字符。
常见陷阱
- 忘记处理 numRows == 1 的特殊情况。
- 在错误时机反转方向，导致行走位。
- 循环内直接字符串相加，造成不必要开销。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) return s;
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
int row = 0;
int step = 1;
for (char ch : s.toCharArray()) {
rows[row].append(ch);
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
StringBuilder ans = new StringBuilder();
for (StringBuilder sb : rows) ans.append(sb);
return ans.toString();
}
}func convert(s string, numRows int) string {
n := len(s)
if numRows == 1 || numRows >= n {
return s
}
rows := make([][]byte, numRows)
row, step := 0, 1
for i := 0; i < n; i++ {
rows[row] = append(rows[row], s[i])
if row == 0 {
step = 1
} else if row == numRows-1 {
step = -1
}
row += step
}
ans := make([]byte, 0, n)
for _, r := range rows {
ans = append(ans, r...)
}
return string(ans)
}class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1 || numRows >= (int)s.size()) return s;
vector<string> rows(numRows);
int row = 0, step = 1;
for (char ch : s) {
rows[row].push_back(ch);
if (row == 0) step = 1;
else if (row == numRows - 1) step = -1;
row += step;
}
string ans;
for (auto& r : rows) ans += r;
return ans;
}
};class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
rows = ["" for _ in range(numRows)]
row, step = 0, 1
for ch in s:
rows[row] += ch
if row == 0:
step = 1
elif row == numRows - 1:
step = -1
row += step
return "".join(rows)var convert = function(s, numRows) {
if (numRows === 1 || numRows >= s.length) return s;
const rows = Array.from({ length: numRows }, () => []);
let row = 0;
let step = 1;
for (const ch of s) {
rows[row].push(ch);
if (row === 0) step = 1;
else if (row === numRows - 1) step = -1;
row += step;
}
return rows.map(r => r.join('')).join('');
};
Comments