【LeetCode Python实现】6. Z 字形变换（中等）

文章目录

• 题目描述
• 示例1
• 示例2
• 示例 3
• 参考代码
• • 方法一：
  • 方法二：

---

题目描述

将一个给定字符串 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.length <= 1000
s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
1 <= numRows <= 1000

示例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字形数据，在遍历生成字符串。

# 320 ms 22.2 MB class Solution: def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s if numRows >= len(s): return s dp = [[False] * len(s) for i in range(numRows)] i = j = 0 flg = 1 for c in s: dp[i][j] = c if flg == -1: i -= 1 j += 1 else: i += 1 if i >= (numRows - 1): flg = flg * -1 j += 1 if i == 0: flg = flg * -1 ret = [c for dpi in dp for c in dpi if c] return "".join(ret)

方法二：

根据方法一的结果发现，我们最终是要把一行的数据再组合为一个字符串，那我可以简单理解为，遍历输入字符串时 i 行的字直接拼接在一起，不起考虑 j。

# 52 ms 15.2 MB class Solution: def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s if numRows >= len(s): return s dp = {i:"" for i in range(numRows)} i = 0 flg = 1 for c in s: dp[i] += c if flg == -1: i -= 1 else: i += 1 if i >= (numRows - 1): flg = flg * -1 if i == 0: flg = flg * -1 ret = [stp for stp in dp.values()] return "".join(ret)