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   N
A P L S I I G
Y   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 = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

Related Topics: String

解題邏輯與實作

基本上這題就是在找規律，有點麻煩的說…

用一個比較好說明的例子，在找規律的時候，我先觀察了直行的部份：

numRows(n) = 5

row0:  0     8         16       24
row1:  1   7 9      15 17     23
row2:  2  6  10   14   18   22
row3:  3 5   11 13     19 21
row4:  4     12        20 

取出各個 row ，直行的部份，會發現它們都是等差數列，其差值可表示為

$2\ast (n-1)$

row0:  0, 8,  16
row1:  1, 9,  17
row2:  2, 10, 18
row3:  3, 11, 19
row4:  4, 12, 20 

另外可以發現，除了第一列與最後一列（row = 0 與 n-1）外，其他列在兩個直行之間會在多輸出一個字元，將這個字元與前一個字元合併用 pair 表示，每一個 pair 都是一個等差，其差值可表示為

$2\ast (n-1-i)$，其中

$i=1,...n-2$。

row1:  (1,7), (9,15),  (17,23)
row2:  (2,6), (10,14), (18,22)
row3:  (3,5), (11,13), (19,21)

此外，需要稍微注意一下corner case，為了簡單起見，我將 numRows 小於等於 1，以及 numRows 大於等於 s 的長度的 case，做了特別判斷，直接將輸入的 s 回傳回去。

class Solution:
  def convert(self, s, numRows):
    if numRows<=1 or numRows >= len(s):
      return s

    result = ""
		
    len_s = len(s)
    max_row_number = numRows-1
    skip_mid_check = False
    for i in range(numRows):
      skip_mid_check = i == 0 or i == numRows-1
      for n in range(i, len_s, 2 * max_row_number):
        result += s[n]
        if not skip_mid_check:
          next_idx = n + 2 * (max_row_number-i)
          if next_idx < len_s:
            result += s[next_idx]
    return result

其他連結

1. 【LeetCode】0000. 解題目錄

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！