6. Z 字形变换

将一个给定字符串 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

字符串模拟

class Solution:
    def __init__(self):
        self.dd = []

    def convert(self, s: str, numRows: int) -> str:
        if not s: return ''
        if numRows == 1: return s
        m, n = len(s), numRows
        self.dd = [['' for _ in range(m)] for _ in range(n)]
        
        self.dd[0][0] = s[0] # 先处理掉第一个字符
        s = ''.join(list(s)[1:]) 
        j = 0

        while s:
            s = self.down(n, j, s)
            if not s: break

            s, j = self.up(j, m, n - 1, s)
            if not s: break

        res = []
        for d in self.dd:
            res.extend(d)
        return ''.join(res)

    def down(self, _n, j, _s):
        _s_l = list(_s)

        for i in range(1, _n):  # 自始至终从第二个位置向下处理
            if not _s_l: break

            pop_s = _s_l.pop(0)
            self.dd[i][j] = pop_s
        return ''.join(_s_l)

    def up(self, _j, _m, _n, _s):
        _s_l = list(_s)

        while _n > 0: # 自始至终从最底部往上开始处理
            if not _s_l: break
            _n -= 1
            _j += 1

            pop_s = _s_l.pop(0)
            self.dd[_n][_j] = pop_s

        return ''.join(_s_l), _j


if __name__ == '__main__':
    obj = Solution()
    res = obj.convert('ABC', 2)
    print(res)

 

上一篇:杨辉三角(力扣)


下一篇:leecode6:Z字形变换