Zigzag Conversion - Leetcode Solution

ZigZag Conversion is a popular string manipulation problem on LeetCode. In this problem, you are given a string and the number of rows to be displayed. You are required to write a program that arranges the characters of the string in a zigzag pattern and returns the new string formed by the arrangement.

For example, if the string is "PAYPALISHIRING" and the number of rows is 3, the zigzag pattern would look like this:

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

The converted string would be "PAHNAPLSIIGYIR".

To solve this problem, we can use an array of strings to store the characters in the zigzag pattern. Initially, we set all the elements in the array to empty strings. Then, we traverse the input string character by character and determine the row and column in the zigzag pattern where the character should be placed.

To determine the row and column, we use two variables - row and step. The variable row tracks the current row, and the variable step tracks the direction we are moving in. Initially, we set row to 0 and step to 1. We move right and up in the zigzag pattern until we reach the top row. When we reach the top row, we change the direction and start moving down and right until we reach the bottom row. We repeat this process until we have placed all the characters in the zigzag pattern.

Here is the Python code to solve the Zigzag Conversion problem:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        
        rows = [''] * numRows
        row = 0
        step = 1
        
        for char in s:
            rows[row] += char
            
            if row == 0:
                step = 1
            elif row == numRows - 1:
                step = -1
            
            row += step
        
        return ''.join(rows)

In the above code, we first check if the number of rows is 1. If it is, we return the input string as it is, since there will be no zigzag pattern to be formed.

Next, we create an array of empty strings, one for each row in the zigzag pattern. We also initialize the variables row and step as 0 and 1, respectively.

We then iterate through each character in the input string and append it to the current row in the zigzag pattern using the += operator. We also change the direction of movement when we reach the top or bottom row.

Finally, we join all the rows in the array into a single string and return it.

This solution has a time complexity of O(n), where n is the length of the input string, since we traverse the string only once to form the zigzag pattern. The space complexity is O(numRows), since we use an array of n empty strings, one for each row in the pattern.

1