难度: 中等
标签: 字符串
将一个给定字符串 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
运行时间: 64 ms
内存: 15.1 MB
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows < 2: return s ans = ["" for _ in range(numRows)] flag = -1 i = 0 for char in s: ans[i] += char if i == 0 or i == numRows-1: flag = -flag i += flag return ''.join(ans)
该题解的思路是模拟Z字形变换的过程。先创建一个长度为numRows的数组ans,数组中的每个元素代表Z字形中的一行。然后遍历字符串s,将每个字符添加到对应行的字符串中。使用变量i表示当前行,flag表示移动方向(向下为1,向上为-1)。当到达第一行或最后一行时,改变移动方向。最后将ans数组中的所有字符串拼接起来即可得到结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows < 2: return s # 创建一个长度为numRows的数组,用于存储每一行的字符串 ans = ["" for _ in range(numRows)] # flag表示移动方向,1为向下,-1为向上 flag = -1 # i表示当前行的索引 i = 0 # 遍历字符串s中的每个字符 for char in s: # 将当前字符添加到对应行的字符串中 ans[i] += char # 当到达第一行或最后一行时,改变移动方向 if i == 0 or i == numRows-1: flag = -flag # 根据移动方向更新当前行的索引 i += flag # 将ans数组中的所有字符串拼接起来即可得到结果 return ''.join(ans)
为什么在`numRows < 2`的情况下直接返回原字符串`s`?
当`numRows`小于2时,无论如何变换,字符串`s`的排列都不会改变。如果只有一行或者字符串为空,则没有必要进行Z字形排列,直接返回原字符串即可,这也避免了后续无意义的计算。
在创建`ans`数组时,为什么选择使用`["" for _ in range(numRows)]`而不是其他初始化方式?
使用`["" for _ in range(numRows)]`是为了初始化一个具体长度为`numRows`的列表,每个元素都是一个空字符串。这种方式确保了每一行都可以直接通过字符串的拼接方法追加字符,从而避免了在使用时再进行类型检查或转换。此外,列表解析是Python中一种简洁且高效的初始化列表的方法。
为什么要使用变量`flag`来控制移动方向,而不是直接使用两个循环分别处理向下和向上的情况?
使用一个变量`flag`来控制移动方向可以使代码更加简洁和易于理解。这种方法避免了编写两个循环的复杂性,而且可以通过简单地改变`flag`的值(+1或-1)来改变遍历的方向。这样,只需一个循环即可完成所有字符的处理,提高了代码的可维护性和实现的效率。
在判断改变移动方向的条件时,为什么是`i == 0 or i == numRows-1`?能否详细解释这个边界条件的含义?
在Z字形变换中,当我们填充到第一行或最后一行时,需要改变字符填充的方向。`i == 0`表示当前填充到了第一行,此时只能向下移动;`i == numRows-1`表示填充到了最后一行,此时只能向上移动。这两个条件是Z字形变换的边界条件,确保字符的填充能够正确地在行之间上下波动,形成Z字形的结构。
最后返回结果时,为什么使用`''.join(ans)`而不是其他拼接字符串的方法?
使用`''.join(ans)`方法拼接字符串列表是Python中推荐的方式,因为它相对于其他方法(如使用`+`运算符逐一拼接)而言,效率更高,特别是在处理较大或较多字符串时。这种方法可以避免多次创建和销毁字符串对象,从而提升程序的性能。