ZigZag Conversion

Problem Id: 6 Difficulty: Medium Tag: String


Intuition

Basically, we can create an empty array and then fill in characters from the original string c one by one.

So the problem becomes, for each index in the original string, find its index after the conversion.

We can start from the second example. The numRows is 4, so it should be something like this.

0     6
1   5 7    11
2 4   8 10
3     9

The sequence can be splitted by several partition, each with length partSize = 2 * numRows - 2. Like below,

0
1   5
2 4
3

The total number of partition (including the last one which might be not filled) is partNum = math.ceil(len(s) / partSize.

We can fill None in to the original string to make the last partition full. Then everything would be simple.The number of each line in zigzag form would be partNum for first and last line and 2 * partNum for other lines.

  1. If ith character is in the first line, where i % partSize == 0, then its position in the final string is i // partSize.
  2. If ith character is between the first point and point in the last line, like 2 and 3, where i % partSize != 0 and i % partSize <= partSize // 2, it's final position should be in line line = i % partSize. And the index is (2 * line - 1) * partNum + 2 * i // partSize.
  3. If ith character is at the last line, its final position is (2 * numRows - 2) * partNum + i // partSize.
  4. And if ith character is at the last edge, like 5 and 6. line = partSize - (i % partSize) + 1. And it's final position is (2 * line - 1) * partNum + 2 * (i // partSize) + 1.

Finally, remove None and join other characters.

Solution


import math


class Solution:
    def convert(self, origin: str, numRows: int) -> str:
        partSize = 2 * numRows - 2
        partNum = math.ceil(len(origin) / partSize)
        target = [None] * (partSize * partNum)

        for i, c in enumerate(origin):
            if i % partSize == 0:
                pos = i // partSize
            elif i % partSize < partSize // 2:
                line = i % partSize
                pos = (2 * line - 1) * partNum + 2 * i // partSize
            elif i % partSize == partSize // 2:
                pos = (2 * numRows - 2) * partNum + i // partSize
            else:
                line = partSize - (i % partSize) + 1
                pos = (2 * line - 1) * partNum + 2 * i // partSize + 1
            target[pos] = c

        target = [c for c in target if c]
        return ''.join(target)