LeetCode-6 - ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

image.png

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"

Solution

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) <= numRows or numRows == 1:
            return s
        l = [''] * numRows
        index = 0
        step = 1
        for i in s:
            l[index] += i
            if index >= numRows - 1:
                step = -1
            elif index <= 0:
                step = 1
            index += step
        return "".join(l)

思路

  1. 首先,要想到结果是一个numRows个元素的list,然后将list中的每个元素相加起来显示即可
  2. 先观察第一列的值,基本的步骤是在遍历字符串的过程中,会将相应的字符置放在list中相应的位置。list的index有时候是+1,有时候是-1,需要有逻辑进行控制。

反思

  1. 解题过程中,想到了用递归来生成每个之形结果,但是递归的结束条件不好找,字符的index跟list的index不好有一个对应关系
  2. 递归结果会将整个问题变得更加复杂
  3. 回过头来看proposal,这种做法简单、自然

你可能感兴趣的