1.题目
将一个给定字符串 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"
- 提示：
- 1 <= s.length <= 1000
- s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
- 1 <= numRows <= 1000
2.题解
C# 解法一：利用二维矩阵模拟
public class Solution { public string Convert(string s, int numRows) { int n = s.Length, r = numRows; if (r == 1 || r >= n) { return s; } int t = r * 2 - 2; int c = (n + t - 1) / t * (r - 1); char[][] mat = new char[r][]; for (int i = 0; i < r; ++i) { mat[i] = new char[c]; } for (int i = 0, x = 0, y = 0; i < n; ++i) { mat[x][y] = s[i]; if (i % t < r - 1) { ++x; // 向下移动 } else { --x; ++y; // 向右上移动 } } StringBuilder ans = new StringBuilder(); foreach (char[] row in mat) { foreach (char ch in row) { if (ch != 0) { ans.Append(ch); } } } return ans.ToString(); } }
- 时间复杂度：O(r⋅n)
- 其中 r=numRows，n 为字符串 s 的长度。时间主要消耗在矩阵的创建和遍历上，矩阵的行数为 r，列数可以视为 O(n)
- 空间复杂度：O(r⋅n)
- 使矩阵需要 O(r⋅n) 的空间。
C# 解法二：压缩矩阵空间
- 方法一中的矩阵有大量的空间没有被使用，能否优化呢？
注意到每次往矩阵的某一行添加字符时，都会添加到该行上一个字符的右侧，且最后组成答案时只会用到每行的非空字符。因此我们可以将矩阵的每行初始化为一个空列表，每次向某一行添加字符时，添加到该行的列表末尾即可。
public class Solution { public string Convert(string s, int numRows) { int n = s.Length, r = numRows; if (r == 1 || r >= n) { return s; } StringBuilder[] mat = new StringBuilder[r]; for (int i = 0; i < r; ++i) { mat[i] = new StringBuilder(); } for (int i = 0, x = 0, t = r * 2 - 2; i < n; ++i) { mat[x].Append(s[i]); if (i % t < r - 1) { ++x; } else { --x; } } StringBuilder ans = new StringBuilder(); foreach (StringBuilder row in mat) { ans.Append(row); } return ans.ToString(); } }
- 时间复杂度：O(n)。
- 空间复杂度：O(n)
- 压缩后的矩阵需要 O(n) 的空间。
Python3 解法三：直接构造
class Solution: def convert(self, s: str, numRows: int) -> str: n, r = len(s), numRows if r == 1 or r >= n: return s t = r * 2 - 2 ans = [] for i in range(r): # 枚举矩阵的行 for j in range(0, n - i, t): # 枚举每个周期的起始下标 ans.append(s[j + i]) # 当前周期的第一个字符 if 0 < i < r - 1 and j + t - i < n: ans.append(s[j + t - i]) # 当前周期的第二个字符 return ''.join(ans)
- 时间复杂度：O(n)
- 其中 n 为字符串 s 的长度。s 中的每个字符仅会被访问一次，因此时间复杂度为 O(n)。
- 空间复杂度：O(1)
- 使返回值不计入空间复杂度。
