Z 字形变换

字符串模拟数学

题目描述

将一个给定的字符串 s 根据给定的行数 rows，以从上往下、从左到右的 Z 字形排列。之后按照逐行阅读的顺序返回拼接后的字符串。

例如，输入字符串 "PAYPALISHIRING"，行数为 4 时，Z 字形排列如下：

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

最终结果为 "PINALSIGYAHRPI"。

思路分析

解法一：模拟法

最直观的做法是模拟 Z 字形书写的过程：

创建一个长度为 rows 的数组，每个元素代表 Z 字形中的一行。
遍历字符串中的每个字符，将它追加到当前行。
通过一个 goingDown 变量控制方向：到达首行或末行时掉头。
最终把所有行拼接起来就是结果。

解法二：数学构造法（进阶）

不需要模拟遍历过程，而是直接通过数学公式计算出每个字符在原字符串中的索引位置。

核心观察：一个完整的 Z 字形周期长度为 cycle = 2 * (rows - 1)。在每个周期中：

下行阶段：每一行都会被经过一次，索引为 j + row。
上行阶段：非首行、非末行会被再经过一次，索引为 j + cycle - row。

因此只需逐行遍历，按公式直接取出字符拼接即可。

示例代码

模拟法

数学构造法

/**
 * Z 字形变换
 * @param s - 原始字符串
 * @param rows - Z 字形排列的行数
 * @returns 按 Z 字形排列后，逐行拼接的结果字符串
 */
export function strZConvert(s: string, rows: number): string {
    // 只有 1 行或字符串长度不足以形成 Z 形，直接返回原字符串
    if (rows === 1 || s.length < rows) {
        return s;
    }

    // 创建一个数组，每个元素代表 Z 字形中的一行，初始为空字符串
    const strRows = new Array(rows).fill("");
    // 当前字符应该放到第几行
    let currRow = 0;
    // 标记当前遍历方向：true 表示从上往下，false 表示从下往上
    let goingDown = false;

    for (const char of s) {
        // 把当前字符追加到对应行
        strRows[currRow] += char;

        // 到达第一行或最后一行时，需要掉头（反转方向）
        if (currRow === 0 || currRow === rows - 1) {
            goingDown = !goingDown;
        }

        // 根据方向移动行号：向下则 +1，向上则 -1
        currRow += goingDown ? 1 : -1;
    }

    // 把所有行拼接起来就是最终结果
    return strRows.join("");
}

/**
 * Z 字形变换 — 进阶数学解法（直接构造法）
 * 不需要模拟遍历过程，而是通过数学公式直接计算每个字符在原字符串中的索引位置。
 * @param s - 原始字符串
 * @param rows - Z 字形排列的行数
 * @returns 按 Z 字形排列后，逐行拼接的结果字符串
 */
export function strZConvertMath(s: string, rows: number): string {
    // 只有 1 行或字符串长度不足以形成 Z 形，直接返回原字符串
    if (rows === 1 || s.length < rows) {
        return s;
    }

    // 一个完整的 Z 字形周期长度：从第 0 行走到第 rows-1 行再折返回第 1 行
    // 例如 rows=4 时，周期为 0→1→2→3→2→1，共 6 步，即 2*(4-1)=6
    const cycle = 2 * (rows - 1);

    let result = "";

    // 逐行构造结果
    for (let row = 0; row < rows; row++) {
        // 在每个周期中，寻找属于当前行的字符
        for (let j = 0; j + row < s.length; j += cycle) {
            // 每个周期的「下行阶段」都会经过当前行一次，索引为 j + row
            result += s[j + row];

            // 对于非首行和非末行，每个周期还有「上行阶段」会再经过当前行一次
            // 上行阶段的索引 = 下一个周期起点 - 当前行号，即 j + cycle - row
            // 首行(row=0)和末行(row=rows-1)在上行阶段不会产生额外字符，
            // 因为它们的上行索引和下行索引重合（首行：j+cycle-0 = 下一周期的下行；末行：j+cycle-(rows-1) = j+rows-1 = 下行索引本身）
            if (row !== 0 && row !== rows - 1 && j + cycle - row < s.length) {
                result += s[j + cycle - row];
            }
        }
    }

    return result;
}

复杂度分析

两种解法的复杂度相同：

时间复杂度：O(n)，其中 n 是字符串长度。每个字符恰好被访问一次。
空间复杂度：模拟法为 O(n)（需要存储各行字符串）；数学构造法也为 O(n)（结果字符串）。

示例演示

以 s = "PAYPALISHIRING"、rows = 4 为例，周期 cycle = 2 * (4 - 1) = 6：

行号	下行索引 (`j + row`)	上行索引 (`j + cycle - row`)	收集到的字符
0	0, 6, 12	—（首行无上行）	P, I, N
1	1, 7, 13	5, 11	A, L, S, I, G
2	2, 8	4, 10	Y, A, H, R
3	3, 9	—（末行无上行）	P, I

逐行拼接结果："PINALSIGYAHRPI"。

#Z 字形变换

#题目描述

#思路分析

#解法一：模拟法

#解法二：数学构造法（进阶）

#示例代码

#复杂度分析

#示例演示