LeetCode 6 - Zigzag Conversion - Python

 

Question:

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)

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:

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

Example 3:

Input: s = "A", numRows = 1

Output: "A"

Answer:

Approach

Try to simulate the behavior of the zigzag iterations.

1. Create an array of strings, where each string is going to represent a row unique row.

2. Create a pointer. The pointer is going to point at a specific row.

3. Iterate through the given string s appending each character to its row using a pointer. Use pointer to imitate the behavior of zigzag iteration.

• The behavior pattern is as follows:
• From the row, go to the down, row appending a new character to a specific string.
• As the pointer reaches the bottom row, make the pointer point one row up at a time, while appending character to a specific row, until the pointer reaches the top row again.
• Repeat this pattern utill you iterate through all characters in the given string s.

4. Join all rows, and return it.

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

        table = ["" for _ in range(numRows)]
        is_beginning = True
        ptr = 0

        for i in range(len(s)):
            if ptr == 0:
                is_beginning = True
            
            if ptr == numRows - 1:
                is_beginning = False
            
            if ptr < numRows and is_beginning:
                table[ptr] += s[i]
                ptr += 1
            
            if not is_beginning:
                table[ptr] += s[i]
                ptr -= 1

        return "".join(table)