Here is the problem:

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

Brainstorming Thinking Process

First method that went through my mind was using an array. But since the maximum length of input string is 1,000 and maximum number of rows is 1,000, most of the memories might not be used which is a huge of waste.

So I thought there must be a logical rule that leads to solution instead of using physical memories.

Step 1. First Valley

First valley is AYPALI in case of number of rows = 4.

For the first row, I could find the following rule:

If a is the index of the previous character and b is the index of the next character,

b = a + (number of rows - 2) x 2 + 1 + 1

To simply, I will say number of rows = k.

1. b = a + 2k - 2

For the second row, we can follow:

b = a + (k - 3) x 2 + 1 + 1

2. b = a + 2k - 4

For the third row, we can follow

b = a + (k - 4) x 2 + 1 + 1

3. b = a + 2k - 6

…

For the last row, we can follow

4. b = a + 2k - 2

which is the same as the first equation.

Step 2. Second Valley

Second valley is SHIRIN in case of number of rows = 4.

We repeat Step 1 reversely.

1. b = a + 2k - 6 (#3 in step 1)

2. b = a + 2k - 4 (#2 in step 1)

3. b = a + 2k - 2 (#1 in step 1)

…

Step 3. Aggregation

For the first row, and the last row, the equation of indexes is

b = a + 2k - 2.

From the next row to the last - 1 row, the equation of indexes is

• If N in Step N is even (N = 0, 2, 4, …)

  b = a + 2k - 2p

  p starts from 1 ~ number of rows.

• If N in Step N is odd (N = 1, 3, 5, …)

  b = a + 2k - 2(k - p + 1)

  (Reverse of the previous rule)

pseudo code

size = len(s)
k = numRows
isEven = False
p = 1

for i in range(1, k + 1): 
    while True: 
        if p > k: p = 1

        if a + 2k - 2 % i == 0: 
            isEven != isEven

        if isEven: 
            b = a + 2k - 2p
        else: 
            b = a + 2k - 2(k - p + 1)

        if b >= size: break 
        print("b", end="")
        a = b    
        p += 1

Submission & Solution

My Code

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        size = len(s)
        result = ""

        if numRows == 1: return s

        for i in range(1, numRows + 1): 
            isEven = False
            prev = i - 1
            if prev >= size:
                result += ""
            else: 
                result += s[prev]

            while True: 
                isEven = not isEven
                if i == 1 or isEven and i != numRows:
                    nex = prev + 2*numRows - 2*i
                else: 
                    nex = prev + 2*numRows - 2*(numRows-i+1)

                if nex >= size: break

                result += s[nex]
                prev = nex

        return result

Solution

Solution given by Leetcode was locked, so I referenced user niits’.

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

        idx, d = 0, 1
        rows = [[] for _ in range(numRows)]

        for char in s:
            rows[idx].append(char)
            if idx == 0:
                d = 1
            elif idx == numRows - 1:
                d = -1
            idx += d

        for i in range(numRows):
            rows[i] = ''.join(rows[i])

        return ''.join(rows)

The main difference between my approach and his is the usage of array.