black paved road surrounding by trees

Convert Zigzag Patterned String in ‘PAYPALISHIRING’ Using Given Number of Rows – Code Solution

The problem of converting a string in a zigzag pattern is a classic problem in computer science and can be solved using a simple iterative approach. The basic idea is to iterate through the characters of the input string, and for each character, calculate its position in the zigzag pattern based on the number of rows specified.

Here’s a possible implementation of the ‘convert’ function in Python:

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

    res = [''] * numRows
    index, step = 0, 1

    for x in s:
        res[index] += x
        if index == 0:
            step = 1
        elif index == numRows -1:
            step = -1
        index += step

    return ''.join(res)

The function takes two arguments as input, a string ‘s’ and an integer ‘numRows’ representing the number of rows in the zigzag pattern. The first if statement checks if the number of rows is 1 or greater than or equal to the length of the input string, in which case the input string is returned as it is.

Otherwise, an empty list ‘res’ is created with ‘numRows’ elements, which will hold the characters in their correct positions in the zigzag pattern. The variable ‘index’ is used to keep track of the current row, and ‘step’ is used to determine whether the next character should be placed on the next row or the current row.

The for loop iterates through the characters of the input string and for each character, the current character is appended to the appropriate element of the ‘res’ list. When the current ‘index’ is 0, the step is set to 1, which means that the next character should be placed on the next row. Similarly, when the current ‘index’ is equal to ‘numRows – 1’, the step is set to -1, which means that the next character should be placed on the previous row. The ‘index’ is then incremented by the value of ‘step’

Finally, the ‘res’ list is joined using the join() method, and the final zigzag pattern string is returned.

Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR”

Input: s = “PAYPALISHIRING”, numRows = 4 Output: “PINALSIGYAHRPI” Explanation: P I N A L S I G Y A H R P I

Input: s = “A”, numRows = 1 Output: “A”

This function has a time complexity of O(n) and a space complexity of O(n) where n is the length of the input string.

Leave a Reply

Your email address will not be published. Required fields are marked *