LeetCode【0006】Z字形变换

1 中文题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING"行数为 3 时，排列如下：

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

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

示例 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\le s.length\le 1000$
• s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
• $1\le numRows\le 1000$

2 求解思路

2.1 基础解法：模拟法

思路
使用多个数组模拟Z字形走位，按照向下和向上两个方向交替移动，在首行和末行时改变移动方向。 模拟的规则：从上到下填充字符时，行号增加；从下到上填充字符时，行号减少；在第一行时向下移动；在最后一行时向上移动。

步骤1: 初始化

• 创建numRows个空数组，每个数组对应一行
• 初始化当前行号和移动方向

步骤2: 遍历字符

• 将每个字符放入对应行的数组中
• 根据当前位置更新移动方向
• 更新当前行号

步骤3: 合并结果

• 将所有行的字符合并成最终字符串

Python代码

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        """
        Z字形变换的模拟法实现
        
        Args:
            s: 输入字符串
            numRows: 指定的行数
            
        Returns:
            按Z字形变换后的字符串
            
        示例:
            输入: s = "PAYPALISHIRING", numRows = 3
            过程: P   A   H   N
                  A P L S I I G
                  Y   I   R
            输出: "PAHNAPLSIIGYIR"
        """
        # 特殊情况处理：当行数为1或字符串长度小于行数时
        if numRows == 1 or numRows >= len(s):
            return s
            
        # 初始化numRows个空字符串数组，用于存储每行的字符
        rows = [[] for _ in range(numRows)]
        
        # 当前行号（表示当前字符应该放在第几行）
        curr_row = 0
        # 移动方向（1表示向下，-1表示向上）
        step = 1
        
        # 遍历字符串中的每个字符
        for char in s:
            # 将当前字符添加到对应行
            rows[curr_row].append(char)
            
            # 在首行或末行时需要改变移动方向
            if curr_row == 0:  # 当前在第一行
                step = 1  # 改为向下移动
            elif curr_row == numRows - 1:  # 当前在最后一行
                step = -1  # 改为向上移动
                
            # 更新当前行号
            curr_row += step
            
        # 合并所有行的字符形成最终结果
        # 先将每一行的字符数组合并成字符串，再将所有行的字符串连接
        return ''.join(''.join(row) for row in rows)

时空复杂度分析

• 时间复杂度：$O(n)$
  • 遍历字符串一次：$O(n)$，其中$n$为字符串长度
  • 合并结果时再次遍历：$O(n)$

总体时间复杂度：$O(n)$

• 空间复杂度：$O(n)$
  • $rows$数组：$O(numRows)$个数组。虽然使用了$numRows$个数组，但所有数组中存储的字符总数仍然是$n$
  • 其他变量：$O(1)$

总体空间复杂度：$O(n)$

2.2 优化解法：数学规律法

思路

蓝框中表示一个周期，蓝框中的字符数即为周期长度。

周期长度 = 2 * numRows - 2

• 向下移动需要 numRows 步
• 向上移动需要 numRows - 2 步（不包括首尾行）
• 总步数 cycle= numRows + (numRows - 2) = 2 * numRows - 2

位置的规律：

• 首行(i=0)和末行(i=numRows-1)：
  • 字符位置：k * cycle ，其中k为周期序号(0, 1, 2, …)
• 中间行：（中间的行，每一行一个周期内只有2个字符）
  • 第一个字符位置：k * cycle + i
  • 第二个字符位置：k * cycle + (cycle - i)
• 末行(i=numRows-1)：
  • 字符位置：k * cycle + i，其中k为周期序号(0, 1, 2, …)

示例：

对于 numRows = 4 的情况，设周期序号为k：

第0行(i=0)：
- 字符位置：6k     (k=0,1,2,...)
- 实际位置：0, 6, 12, ...

第1行(i=1)：
- 第一个字符位置：6k + 1   (k=0,1,2,...)
- 第二个字符位置：6k + 5   (k=0,1,2,...)
- 实际位置：1, 5, 7, 11, 13, ...

第2行(i=2)：
- 第一个字符位置：6k + 2   (k=0,1,2,...)
- 第二个字符位置：6k + 4   (k=0,1,2,...)
- 实际位置：2, 4, 8, 10, 14, ...

第3行(i=3)：
- 字符位置：6k + 3     (k=0,1,2,...)
- 实际位置：3, 9, 15, ...

python代码

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        """
        使用数学方法实现Z字形变换
        
        核心思想：
        1. 找出Z字形排列的周期规律
        2. 通过数学公式直接计算每个字符在结果中的位置
        
        参数说明：
        s: 输入字符串
        numRows: Z字形的行数
        
        示例分析：
        对于 numRows = 4 的情况：
        周期 = 2 * numRows - 2 = 6
        P     I    N
        A   L S  I G
        Y A   H R
        P     I
        
        规律分析：
        第0行: 0,     6,     12    -> 间隔6 (周期)
        第1行: 1,   5,7,   11,13   -> 间隔4,2,4,2
        第2行: 2, 4, 8,10, 14      -> 间隔2,4,2,4
        第3行: 3,     9,     15    -> 间隔6 (周期)
        """
        # 特殊情况处理
        if numRows == 1 or numRows >= len(s):
            return s
            
        # 计算周期长度
        cycle = 2 * numRows - 2
        
        # 存储结果
        result = []
        
        # 遍历每一行
        for i in range(numRows):
            # 遍历每个周期的起始位置
            for j in range(0, len(s), cycle):
                # 添加当前周期的第一个字符（如果存在）
                if j + i < len(s):
                    result.append(s[j + i])
                    
                # 对于中间行（非首尾行），添加当前周期的第二个字符（如果存在）
                if i != 0 and i != numRows - 1:  # 不是首行也不是末行
                    # 计算当前周期中第二个字符的位置
                    second_pos = j + cycle - i
                    if second_pos < len(s):
                        result.append(s[second_pos])
                        
        # 合并所有字符
        return ''.join(result)

时空复杂度分析

• 时间复杂度
  • 外层循环：遍历每一行O(numRows)
  • 内层循环：每行处理约 n/cycle个字符

总的字符处理数量仍然是 n，因此总时间复杂度为 O(n)

• 空间复杂度
  • 结果数组：存储所有字符，O(n)
  • 其他变量：O(1)

总空间复杂度：O(n)

2.3 最优解法：字符串拼接法

思路
把Z字形看作是在若干行之间来回移动的过程，记录每一行的字符，最后拼接起来。具体实现步骤

• 初始化
  • 创建numRows个空字符串，每个字符串对应一行
  • 设置当前行号curRow = 0
  • 设置移动方向step = 1（1表示向下，-1表示向上）
• 遍历原字符串
  • 把当前字符添加到当前行对应的字符串中
  • 根据当前位置更新移动方向：
    • 到达第一行(curRow = 0)时，向下移动(step = 1)
    • 到达最后一行(curRow = numRows-1)时，向上移动(step = -1)
  • 更新当前行号：curRow += step
• 合并结果
  • 将所有行的字符串按从上到下的顺序拼接起来

示例
以字符串 “PAYPALISHIRING” 和 numRows = 4 为例：

初始状态：
row[0] = ""
row[1] = ""
row[2] = ""
row[3] = ""

逐字符处理：
P: 放入第0行，向下移动
row[0] = "P"
row[1] = ""
row[2] = ""
row[3] = ""

A: 放入第1行，继续向下
row[0] = "P"
row[1] = "A"
row[2] = ""
row[3] = ""

Y: 放入第2行，继续向下
row[0] = "P"
row[1] = "A"
row[2] = "Y"
row[3] = ""

P: 放入第3行，改为向上移动
row[0] = "P"
row[1] = "A"
row[2] = "Y"
row[3] = "P"

A: 放入第2行，继续向上
row[0] = "P"
row[1] = "A"
row[2] = "YA"
row[3] = "P"

...以此类推

python代码

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        """
        使用字符串拼接法实现Z字形变换
        
        核心思想：
        1. 创建numRows个字符串，分别对应每一行
        2. 遍历原字符串，将每个字符追加到对应行的字符串中
        3. 设置方向标志，在到达边界时改变方向
        4. 最后将所有行的字符串拼接起来
        
        参数说明：
        s: 输入字符串
        numRows: Z字形的行数
        
        返回值：
        返回Z字形变换后的字符串
        """
        # 特殊情况处理
        if numRows == 1 or numRows >= len(s):
            return s
            
        # 初始化每一行的字符串
        rows = [''] * numRows
        
        # 当前行号
        cur_row = 0
        # 移动方向，1表示向下，-1表示向上
        step = 1
        
        # 遍历每个字符
        for c in s:
            # 将当前字符添加到对应行
            rows[cur_row] += c
            
            # 在首行时向下移动
            if cur_row == 0:
                step = 1
            # 在末行时向上移动
            elif cur_row == numRows - 1:
                step = -1
                
            # 更新当前行号
            cur_row += step
            
        # 合并所有行的字符串
        return ''.join(rows)

时空复杂度分析

• 时间复杂度：O(n)
  • 遍历字符串一次：O(n)
  • 字符串拼接操作：O(1)
  • 最后合并所有行：O(n)
• 空间复杂度：O(n)
  • rows数组：存储n个字符，O(n)
  • 其他变量：O(1)

3 题目总结

题目难度：中等
数据结构： 字符串
应用算法： 数学规律