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. 首先，要想到結(jié)果是一個(gè)numRows個(gè)元素的list，然后將list中的每個(gè)元素相加起來顯示即可
2. 先觀察第一列的值，基本的步驟是在遍歷字符串的過程中，會(huì)將相應(yīng)的字符置放在list中相應(yīng)的位置。list的index有時(shí)候是+1，有時(shí)候是-1，需要有邏輯進(jìn)行控制。

反思

1. 解題過程中，想到了用遞歸來生成每個(gè)之形結(jié)果，但是遞歸的結(jié)束條件不好找，字符的index跟list的index不好有一個(gè)對(duì)應(yīng)關(guān)系
2. 遞歸結(jié)果會(huì)將整個(gè)問題變得更加復(fù)雜
3. 回過頭來看proposal，這種做法簡單、自然