We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Zigzag Conversion

Difficulty: Medium

Problem Description

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows. The task is to convert a given string into this zigzag pattern and then read it line by line to return the final string representation.

Key Insights

  • The zigzag pattern alternates between moving downwards and upwards across the specified number of rows.
  • The characters are collected in each row as they are traversed, and once the traversal is complete, the rows are concatenated to form the final string.
  • If the number of rows is 1, the output is the original string since zigzag conversion does not apply.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n), for storing the characters in the zigzag format.

Solution

To solve this problem, we can use a list of strings (or an array of strings) to represent each row of the zigzag pattern. We iterate through the characters of the input string and determine their positions in the zigzag pattern based on the current row and direction (downwards or upwards). After populating the rows, we concatenate them to get the final result.

Code Solutions

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

    rows = [''] * numRows
    current_row = 0
    going_down = False

    for char in s:
        rows[current_row] += char
        if current_row == 0:
            going_down = True
        elif current_row == numRows - 1:
            going_down = False

        current_row += 1 if going_down else -1

    return ''.join(rows)
← Back to All Questions