動機

只要看出怎麼遞迴，剩下就是細心的問題

Problem

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)

P   A   H   NA P L S I I GY   I   R

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 s, int numRows);

 

Example 1:

Input: s = PAYPALISHIRING, numRows = 3Output: PAHNAPLSIIGYIR

Example 2:

Input: s = PAYPALISHIRING, numRows = 4Output: PINALSIGYAHRPIExplanation:P     I    NA   L S  I GY A   H RP     I

Example 3:

Input: s = A, numRows = 1Output: A

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Sol

可以把pattern切成下面的樣子

P   | A   | H   | N
A P | L S | I I | G
Y   | I   | R

這樣就可以把整個分成

(row是3，總長n是2*row-2在此是4)

P(i:0)
A(i:1) P(i:n-1)
Y(i:n-2)

(row是4，總長n是2*row-2在此是6)

P(i:0)
A(i:1)    L(i:n-1)
Y(i:2) A(i:n-2)
P(i:n-3)

這樣就可以解了

class Solution:
    def convert(self, s: str, n: int) -> str:
        if n == 1:
            return s
        sub_len = (n-1)*2
        
        ret = []
        for i in range(n):
            start = 0
            while start < len(s):
                sub = s[start:start+sub_len]
                if i == 0 or i == n-1:
                    if i < len(sub):
                        ret.append(sub[i])
                else:
                    if i < len(sub):
                        ret.append(sub[i])
                    if sub_len-i < len(sub):
                        ret.append(sub[sub_len-i])
                start += sub_len
        return ''.join(ret)

第一個就是