---
title: 【LeetCode】0006. ZigZag Conversion
date: 2018-12-19
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

<br>

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)
<!--more-->

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

And then read line by line: `"PAHNAPLSIIGYIR"`
<br>

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

<br>

**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 

<br>

取出各個 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 

<br>

另外可以發現，除了第一列與最後一列（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)

<br>

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

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. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0006-ZigZag-Conversion) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0006-ZigZag-Conversion)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！