題目

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)

1
2
3
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

1
2
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2

1
2
3
4
5
6
7
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3

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

Constraints:

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

解釋題目

給定一個字串 s 和一個整數 numRows，將字串按 Z 字形排列後再逐行讀出，輸出結果字串。
輸入: s = PAYPALISHIRING, numRows = 3

Z 字形排列如下： 

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

輸出: PAHNAPLSIIGYIR

思路

  1. 透過 numRows 可以知道最後呈現的 Z 字型有幾列
  2. 所以在遍歷字串的時候，可以記住每個字母在哪一列，把同一列的字母放在一起
  3. 一開始先給予一個陣列 rows，陣列大小是 numRows 分別存入每列的字母，若 numRows = 3，則 rows = ["", "", ""]
  4. 方向很重要，如果目前所在列 cur_row 是第 0 列或是最後一列，就要轉向
  5. 假設轉向與否是一個變數 going_down，遇到上述狀況，going_down = not going_down
  6. 根據 going_down 是否為真，來決定 cur_row 要遞增還是遞減
    • going down = true，cur_row + 1
    • going down = false，cur_row - 1
  7. 特殊情況要特別注意:
    • 如果 numRows 是 1，無法走 Z 型，所以直接回傳 s
    • 如果 numRows >= len(s)，也是無法走 Z 型，所以直接回傳 s

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 每一列的字串先給空字串，共有 numRows 列
        rows = ["" for i in range(numRows)]
        going_down = False
        cur_row = 0

        for char in s:
            # 根據目前是第幾列，塞字串到那一列
            rows[cur_row] += char
            if cur_row == 0 or cur_row == numRows - 1:
                # 在第 0 列或最後一列，要轉向
                going_down = not going_down

            # 判斷 cur_row 目前在哪一列
            if going_down:
                cur_row += 1
            else:
                cur_row -= 1

        return "".join(rows)