0006.Z字形变换

难度：🟡 中等

标签：字符串

链接：6. Z 字形变换

题目描述

将一个给定字符串 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"

解题思路

核心思想

本题的核心是模拟将字符串字符按照“Z”字形顺序填入一个虚拟的二维网格中，然后按行读出。我们不必真正创建一个二维网格，而是可以直接模拟这个填充过程，确定每个字符应该属于哪一行。

思路选择

按行模拟法 是解决此问题的最直观、最高效的思路。

• 我们可以创建一个数组，其长度为 numRows，数组中的每个元素都是一个字符串，代表 Z 字形排列的一行。

• 我们遍历输入的字符串 s，对于每一个字符，我们将其追加到正确的行字符串末尾。

• 关键在于如何控制当前字符应该被放入哪一行。我们可以用一个指针 currentRow 来追踪当前行号，并用一个方向变量 direction 来控制行号是应该增加（向下走）还是减少（向上走）。当行号到达顶部（第 0 行）或底部（第 numRows - 1 行）时，就改变方向。

关键步骤

1. 处理边界情况：如果 numRows 为 1，Z 字形就是其本身，直接返回原字符串 s。

2. 初始化：

   • 创建一个结果数组 rows，其长度为 numRows，每个元素初始化为空字符串。

   • 初始化当前行指针 currentRow = 0。

   • 初始化方向 direction = -1（初始为-1，这样第一次循环就会变为1，开始向下走）。

3. 循环遍历：遍历输入字符串 s 中的每一个字符。 a. 将当前字符追加到 rows[currentRow]。 b. 改变方向：如果 currentRow 到达了顶部（0）或底部（numRows - 1），则将 direction 乘以 -1 来反转方向。 c. 移动行指针：currentRow += direction。

4. 返回结果：遍历结束后，将 rows 数组中的所有字符串连接起来，即为最终结果。

代码实现

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows === 1) {
        return s;
    }

    const rows = new Array(numRows).fill('');
    let currentRow = 0;
    let direction = -1; // 1 for down, -1 for up

    for (const char of s) {
        rows[currentRow] += char;
        // 当到达顶部或底部时，改变方向
        if (currentRow === 0 || currentRow === numRows - 1) {
            direction = -direction;
        }
        currentRow += direction;
    }

    return rows.join('');
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是字符串 s 的长度。我们只需要对字符串进行一次完整的遍历。

• 空间复杂度：O(n) 我们需要一个额外的数组来存储 numRows 个字符串，这些字符串的总长度等于输入字符串 s 的长度。

相关题目

• 0054.螺旋矩阵

• 0048.旋转图像

总结

本题是字符串模拟问题的经典范例。其解题的关键在于准确地捕捉 Z 字形路径的规律，并用一个方向变量和边界判断来控制字符的填充逻辑。这种按行处理的思路避免了复杂的二维坐标计算，使得解法既直观又高效。