# Leetcode 6 Solution

https://leetcode.com/problems/zigzag-conversion

## Thinking Process

This question requires us to find out the pattern of the final string.

• The chars of the first line of the zigzag locate at `2 * (n - 1) * k`.
• The chars of the second line of the zigzag locate at `1 + 2 * (n - 1) * k` and `2 * (n - 1) - 1 + 2 * (n - 1) * k`.
• The chars of the third line of the zigzag locate at `2 + 2 * (n - 1) * k` and `2 * (n - 1) - 2 + 2 * (n - 1) * k`.
• The chars of the fourth line of the zigzag locate at `3 + 2 * (n - 1) * k` and `2 * (n - 1) - 3 + 2 * (n - 1) * k`.
• The chars of the last line of the zigzag locate at `n - 1 + 2 * (n - 1) * k`.

In all above cases, `k` iterate from `0` to a number where the index exceeds the size of the string.

## Time & Space Complexity

Assuming N is the size of the array, the time & space compelxities are:

• Time complexity: `O(N)`
• Space complexity: `O(N)`

## Solution

``````class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
n = numRows

if n == 1:
return s

res = ""

# Append the first line.
i = 0
while i < len(s):
res += s[i]
i += 2 * (n - 1)

# Append the middle lines.
first_l = 1
first_r = 2 * (n - 1) - 1

while first_l < first_r:
l = first_l
r = first_r

while l < len(s):
res += s[l]
if r < len(s):
res += s[r]
l += 2 * (n - 1)
r += 2 * (n - 1)

first_l += 1
first_r -= 1

# Append the last line.
i = n - 1
while i < len(s):
res += s[i]
i += 2 * (n - 1)

return res
``````