6. Z 字形变换
题目描述
输入字符串 s 和行数 numRows。把 s 的字符依次写进 numRows 行：先在第一列从第 1 行竖直向下写到最后一行，再沿斜线向右上方一行一行往回写，到第 1 行后又竖直向下，如此反复，形成 Z 字形。
例如 "PAYPALISHIRING" 写成 3 行时，第 1 行依次是 P A H N，第 2 行是 A P L S I I G，第 3 行是 Y I R。
写完后，按行从上到下、每行从左到右把字符连起来，返回得到的新字符串。numRows 为 1 时字符串保持原样。
示例 1
输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"
解释：按 3 行排列后，三行分别是 PAHN、APLSIIG、YIR，连起来即为答案。
示例 2
输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI"
解释：按 4 行排列后，四行分别是 PIN、ALSIG、YAHR、PI。
示例 3
输入：s = "A", numRows = 1 输出："A"
解释：只有一行，字符串不变。
数据范围
1 <= s.length <= 1000s只含大小写英文字母、','和'.'。1 <= numRows <= 1000
解题思路：按行模拟折返
不必真的画出二维图形，只需知道每个字符落在哪一行。准备 numRows 个字符串，用 r 表示当前行、step 表示方向。逐个字符放入 rows[r]；到第 0 行时方向变为向下，到最后一行时方向变为向上。最后把各行拼接起来。numRows = 1 时无法折返，直接返回 s。
为什么正确
处理完前 i 个字符后，rows[j] 恰好按顺序包含前 i 个字符中落在第 j 行的那些字符。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
numRows = 1 时 r 在 0 和 numRows-1 重合，step 会先变 +1，导致 r 越界，必须特判。另外行数大于字符串长度时也没有问题，只是下面的行为空。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
rows = [''] * numRows
r, step = 0, 1
for c in s:
rows[r] += c
if r == 0:
step = 1
elif r == numRows - 1:
step = -1
r += step
return ''.join(rows)class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
int r = 0, step = 1;
for (char c : s.toCharArray()) {
rows[r].append(c);
if (r == 0) {
step = 1;
} else if (r == numRows - 1) {
step = -1;
}
r += step;
}
StringBuilder ans = new StringBuilder();
for (StringBuilder row : rows) ans.append(row);
return ans.toString();
}
}class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) {
return s;
}
vector<string> rows(numRows);
int r = 0, step = 1;
for (char c : s) {
rows[r] += c;
if (r == 0) {
step = 1;
} else if (r == numRows - 1) {
step = -1;
}
r += step;
}
string ans;
for (auto& row : rows) ans += row;
return ans;
}
};func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
rows := make([][]byte, numRows)
r, step := 0, 1
for i := 0; i < len(s); i++ {
rows[r] = append(rows[r], s[i])
if r == 0 {
step = 1
} else if r == numRows-1 {
step = -1
}
r += step
}
ans := []byte{}
for _, row := range rows {
ans = append(ans, row...)
}
return string(ans)
}var convert = function(s, numRows) {
if (numRows === 1) {
return s;
}
const rows = new Array(numRows).fill('');
let r = 0, step = 1;
for (const c of s) {
rows[r] += c;
if (r === 0) {
step = 1;
} else if (r === numRows - 1) {
step = -1;
}
r += step;
}
return rows.join('');
};function convert(s: string, numRows: number): string {
if (numRows === 1) {
return s;
}
const rows = new Array<string>(numRows).fill('');
let r = 0, step = 1;
for (const c of s) {
rows[r] += c;
if (r === 0) {
step = 1;
} else if (r === numRows - 1) {
step = -1;
}
r += step;
}
return rows.join('');
}其他解法
模拟法按读入顺序把字符分配到各行；周期法按输出顺序直接算出每行该取的下标。两者都是 O(n)。
解法 2：按周期直接计算下标 时间 O(n)，空间 O(1)
Z 字形每 2*numRows-2 个字符构成一个周期 cycle。逐行输出：第 i 行在每个周期起点 j 处取 s[j+i]；中间行（0<i<numRows-1）还要再取斜线上的 s[j+cycle-i]。下标越界就跳过。
不需要先把字符分到各行的缓冲区，除答案外只用 O(1) 空间。要先推出周期和斜线下标公式，不如模拟直观。
class Solution:
def convert(self, s: str, numRows: int) -> str:
n = len(s)
if numRows == 1 or numRows >= n:
return s
cycle = 2 * numRows - 2
ans = []
for i in range(numRows):
for j in range(0, n - i, cycle):
ans.append(s[j + i])
if 0 < i < numRows - 1 and j + cycle - i < n:
ans.append(s[j + cycle - i])
return ''.join(ans)class Solution {
public String convert(String s, int numRows) {
int n = s.length();
if (numRows == 1 || numRows >= n) return s;
int cycle = 2 * numRows - 2;
StringBuilder ans = new StringBuilder();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycle) {
ans.append(s.charAt(j + i));
if (i > 0 && i < numRows - 1 && j + cycle - i < n) ans.append(s.charAt(j + cycle - i));
}
}
return ans.toString();
}
}class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if (numRows == 1 || numRows >= n) return s;
int cycle = 2 * numRows - 2;
string ans;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycle) {
ans += s[j + i];
if (i > 0 && i < numRows - 1 && j + cycle - i < n) ans += s[j + cycle - i];
}
}
return ans;
}
};func convert(s string, numRows int) string {
n := len(s)
if numRows == 1 || numRows >= n {
return s
}
cycle := 2*numRows - 2
ans := make([]byte, 0, n)
for i := 0; i < numRows; i++ {
for j := 0; j+i < n; j += cycle {
ans = append(ans, s[j+i])
if i > 0 && i < numRows-1 && j+cycle-i < n {
ans = append(ans, s[j+cycle-i])
}
}
}
return string(ans)
}var convert = function(s, numRows) {
const n = s.length;
if (numRows === 1 || numRows >= n) return s;
const cycle = 2 * numRows - 2;
const ans = [];
for (let i = 0; i < numRows; i++) {
for (let j = 0; j + i < n; j += cycle) {
ans.push(s[j + i]);
if (i > 0 && i < numRows - 1 && j + cycle - i < n) ans.push(s[j + cycle - i]);
}
}
return ans.join('');
};function convert(s: string, numRows: number): string {
const n = s.length;
if (numRows === 1 || numRows >= n) return s;
const cycle = 2 * numRows - 2;
const ans: string[] = [];
for (let i = 0; i < numRows; i++) {
for (let j = 0; j + i < n; j += cycle) {
ans.push(s[j + i]);
if (i > 0 && i < numRows - 1 && j + cycle - i < n) ans.push(s[j + cycle - i]);
}
}
return ans.join('');
};