ZigZag Conversion – LeetCode Solutions

by

LeetCode has a hard coding Problem in Its’ Algorithm Section: “ZigZag Conversion of Given String”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE.

ZigZag Conversion

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);
Examples
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"
Conditions
  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Solution to Zigzag Conversion

The Skeleton Code given in LeetCode is

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """

Firstly, Check for the Least Possible Solution. In which we are given an input String with Number of Rows = 1, In this case, it should return the same input string.

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if n == 1:    
            return s

Secondly, Create an array of size equal to String length.

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if n == 1:    
            return s
        
        l = len(s)

        arr=["" for x in range(l)]

Set the row to 0 and the orientation to “down.” The direction determines whether we should go in rows up or down. Go over the input string(loop).

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if n == 1:    
            return s
        
        l = len(s)

        arr=["" for x in range(l)]
        down = True
        row = 0
        for i in range(l):

Add the current character to the current row’s string. Change the orientation to ‘up’ if the row number is n-1. Change the orientation to ‘down’ if the row number is 0. Row++ if the direction is down. Otherwise, row–. Return the String.

Complete Code:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1:
            return s
        
        l = len(s)


        arr=["" for x in range(l)]
        row = 0
        
        for i in range(l):

            arr[row] += s[i]

            if row == numRows - 1:
                down = False

            elif row == 0:
                down = True

            if down:
                row += 1
            else:
                row -= 1

        # Print concatenation
        # of all rows
        final = ""
        for i in range(l):
            final += arr[i]
        return final

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE