Today, we have another interesting challenge from Leetcode (https://leetcode.com/problems/zigzag-conversion/); we’re going to scramble a given word following a zig zag fashion.
For instance, let’s consider the word PROGRAMMING. If we write this word in a zig zag fashion using 3 rows, we’ll get
From this zig zag layout, we can then concatenate each row to get the string PRIRGAMNOMG.
If we write the word in a zig zag fashion using 4 rows, we’ll get
The resulting string is thus PMRAMORIGGN.
Our job is to write a program to scramble a given string using the zigzag layout described above. In other words, if given the word PROGRAMMING and asked to scramble it into 3 rows of zigzag letters, our program should return the string PRIRGAMNOMG.
This program takes in two arguments – the original string and the number of rows. Got it? Try coding it yourself.
Hint
One easy way to do it is to iterate through the given string one character at a time and assign the character to the correct row. For instance, if the number of rows is 3 and the string is PROGRAMMING, we can iterate through the string and assign ‘P’ to row 0, ‘R’ to row 1, ‘O’ to row 2, ‘G’ to row 1, ‘R’ to row 0, ‘A’ to row 1 etc.
Note that in the description above, we refer to the first, second and third rows as row 0, row 1 and row 2 respectively, to be in line with the zero-based indexing used in programming.
Solution
def convert(s, numRows):
result = [""] * numRows
rowNumber = 0
direction = 1
for i in range(len(s)): #looping through each element
result[rowNumber] = result[rowNumber] + s[i]
if rowNumber < numRows -1 and direction == 1:
rowNumber += 1
elif rowNumber > 0 and direction == -1:
rowNumber -= 1
else:
direction *= -1
rowNumber += direction
return ''.join(result)
Run Through
Here, we declare a function called convert with two parameters – s and numRows.
Within the function, we first declare and initialize a list called result using the statement
result = [""] * numRows
The number of elements in result depends on the value of numRows. For instance, if numRows equals 3, result = ['', '', ''].
Next, we declare two variables called rowNumber and direction.
rowNumber tracks the current row to assign letters to, while direction tracks whether we are moving vertically down or diagonally up the zigzag. Positive 1 indicates that we are moving down (e.g. from row 0 to row 1) while -1 indicates that we are moving up (e.g. from row 2 to row 1).
After declaring the variables, we use a for loop to iterate through the string one character at a time.
We use the line
result[rowNumber] = result[rowNumber] + s[i]
to concatenate the current letter (s[i]) to the current row (whose row number is tracked by the variable rowNumber).
Next, we determine if we should move up or down to the next row. If direction equals 1 and we have not reached the last row (i.e. rowNumber < numRows – 1), we move down (rowNumber += 1).
Else, if direction equals -1 and we have not reached the top row (rowNumber > 0), we move up (rowNumber -= 1).
Last but not least, if we are moving down and have reached the last row, or we are moving up and have reached the first row, we change the value of direction (direction *= -1) and move up or down accordingly.
Once we finish iterating through the entire string, we concatenate each of the elements in result using the join() method and return the result.
Confused?
Example
Let’s look at a concrete example of how this works. Suppose numRows equals 3 and s equals 'PROGRAMMING'.
When the function first starts, result = ['', '', ''], rowNumber = 0 and direction = 1.
Within the for loop, we first concatenate 'P' to result[0]. Hence, result[0] = 'P'.
Next, as rowNumber < numRows – 1 (0 < 2) and direction equals 1, the if block is executed and rowNumber is incremented to 1.
Next, we iterate to the second letter 'R'. As rowNumber equals 1 now, we concatenate 'R' to result[1]. Hence, result[1] = 'R'.
Similarly, the if block condition evaluates to True. Hence, the if block is executed and rowNumber is incremented to 2.
We then come to the third letter 'O'. As rowNumber equals 2, we concatenate 'O' to result[2]. Hence, result[2] = 'O'.
After concatenating, we come to the if statement.
Currently, rowNumber equals 2 and numRows – 1 = 3 – 1 = 2.
As 2 < 2 is not true, the if block is no longer executed. Similarly, the elif block is not executed as direction == -1 is not true.
The else block is executed instead.
Here, we multiply direction by -1. This has the effect of changing a positive number to a negative number and vice versa.
direction thus becomes -1.
The next statement (rowNumber += direction) effectively becomes rowNumber = rowNumber + (-1), which decrements rowNumber by 1. rowNumber thus becomes 2-1 = 1.
When we iterate to the next character 'G', we concatenate 'G' to result[1]. Hence, result[1] = 'RG'.
Next, we reach the if statement. The if block is not executed as direction is not equal to -1. Instead, the elif block is executed as rowNumber > 0 and direction equals -1. rowNumber is thus decremented to 0.
When we iterate to the next character 'R', we concatenate 'R' to result[0]. Hence, result[0] = 'PR'.
Next, we reach the if statement. Both the if and elif blocks evaluate to False. As a result, the else block is executed and direction is changed to 1. The next statement (rowNumber += direction) becomes rowNumber = rowNumber + 1, which results in rowNumber being incremented by 1. rowNumber thus becomes 1.
This sequence of modifying the value of rowNumber and direction repeats until the end of the given string is reached.
Once that is done, we use the built-in join() function to join the three elements in result into a single string and return this string as the result.
Clear?