Geek Culture
Published in

Geek Culture

ZigZag String Conversion in python

How to convert your string to a zigzag string in python

Introduction:

This post discusses the solution for zigzag string conversion in leetcode. Please note that there may be multiple solutions for this problem and the solution discussed here is just one among them. Any alternative or better solutions are welcome.

Problem Statement:

Given a string, convert the string to zigzag format and print the output.

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:

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"

Brainstorming:

We have been given a string of length n and number of rows to display the string. The idea here is not to print the string in the zigzag format, rather to print the output if it was written in the zigzag format.

For instance, the string PAYPALISHIRING has to be written as PAHNAPLSIIGYIR, the idealogy here is, the characters PAHN appear in row 1, APLSIIG appear in row 2 and YIR appear in row 3.

The moment we see this problem, we inherently think in the lines of printing the string character by character on consecutive rows. Trust me, that’s exactly what I was doing initially. However, if you read the problem statement carefully, all we need is to print the output like it is converted to zigzag format.

Solution:

Let’s say the number of rows is 3, create a list with empty strings equal to the number of rows provided. The reason we create this list is, every row in the zigzag string corresponds to an index in this list.

Now, the first row should have the characters PAHN, which means they should be added to the first index of the list. Similarly, APLSIIG in index 2 and YIR in index 3 of the list respectively.Of course, we may not know the order of characters before we solve, unless we literally write the zigzag order on a paper.

All we have is the string and the number of rows.We should leverage the number of rows field to arrive at this solution.

Code:

zigzag step 1

Output:

['PAYPALISHIRING', '', '']

Well!! well!! We have taken our baby steps in solving this. We have initialised a line_no variable to add characters from the string in corresponding indices.However, one pitfall here is all characters are being added to the first index. We need to split the characters and add them to different indices.

To do this, we need a variable to go back and forth between the indices. Basically traverse through the positive and negative indices. Now we will introduce a second variable to do this.

zig zag step 2

We have introduced a switcher variable that will traverse through the list. We multiply it with -1 as and when we hit the 0th index or the last index. To give a clearer picture, I have added print statements for each iteration. Let’s see the output now.

['P', '', '']
['P', 'A', '']
['P', 'A', 'Y']
['PP', 'A', 'Y']
['PPA', 'A', 'Y']
['PPAL', 'A', 'Y']
['PPALI', 'A', 'Y']
['PPALIS', 'A', 'Y']
['PPALISH', 'A', 'Y']
['PPALISHI', 'A', 'Y']
['PPALISHIR', 'A', 'Y']
['PPALISHIRI', 'A', 'Y']
['PPALISHIRIN', 'A', 'Y']
['PPALISHIRING', 'A', 'Y']
['PPALISHIRING', 'A', 'Y']
None

Now, we still don’t have the desired output. However, based on the switcher variable, w e see that the characters get added to the corresponding index in the list.Finally, all we need to do is join the characters in the string and handle the corner case of rows < 1.

Below is the final and complete code.

zigzag final code

Output:

PAHNAPLSIIGYIR

If you wish to see the intermediate output, add print statements like we did in the previous code.

['P', '', '']
['P', 'A', '']
['P', 'A', 'Y']
['P', 'AP', 'Y']
['PA', 'AP', 'Y']
['PA', 'APL', 'Y']
['PA', 'APL', 'YI']
['PA', 'APLS', 'YI']
['PAH', 'APLS', 'YI']
['PAH', 'APLSI', 'YI']
['PAH', 'APLSI', 'YIR']
['PAH', 'APLSII', 'YIR']
['PAHN', 'APLSII', 'YIR']
['PAHN', 'APLSIIG', 'YIR']

Summary:

  • The zigzag leetcode challenge is of difficulty medium.
  • If you get an index error while solving in an interview, check if you are adding line_no with the switcher variable or whatever you call it and not with primitive 1. I've personally made this mistake.
  • The time complexity of this solution is O(s) where s is the length of the string.

Please feel free to propose alternative solutions. All the very best.

Originally published at https://dock2learn.com on June 9, 2022.

--

--

A new tech publication by Start it up (https://medium.com/swlh).

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store