ZigZag Conversion (in Python)

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this :

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line : "PAHNAPLSIIGYIR"

Solution

Approach 1 : Sort by Row

Intuition

By iterating through the string from left to right, we can easily determine which row in the Zig-Zag pattern that a character belongs to.

Algorithm

1. We can use min(numRows, len(s)) lists to represent the non-empty rows of the Zig-Zag pattern.

2. Iterate through s from left to right, appending each character to the appropriate row. The appropriate row can be tracked using two variables: the current row and the current direction.

3. The current direction changes only when we moved up to the topmost row or moved down to the bottommost row.

def convert(self, s, numRows):
 
    if numRows <= 1 :
        return s
 
    n = len(s)
    arr = [""]*numRows
 
    dr = 1
    x = 0
 
    for i in range(n) :
 
        arr[x] += s[i]
        x += dr
 
        # 맨 위 / 맨 아래일 때
        if x == numRows-1 or x == 0 :
            dr *= -1
        
    ans = ""
 
    for i in range(numRows) :
        ans += arr[i]
 
    return ans

Complexity Analysis

•Time Complexity: O(n), where n == len(s)

•Space Complexity: O(n)

---

Approach 2 : Visit by Row

Intuition

Visit the characters in the same order as reading the Zig-Zag pattern line by line.

Algorithm

Visit all characters in row0 first, then row1, then row2, and so on...

For all whole numbers k,

•Characters in row0 are located at indexed k(2*numRows-2)

•Characters in row numRows-1 are located at indexes k(2*numRows-2)+numRows-1

•Characters in inner row i are located at indexes k(2*numRows-2)+i and (k+1)(2*numRows-2)-i.

def convert(self, s, numRows):
 
    if numRows <= 1 :            
        return s
 
    n = len(s)
    ans = ""
    interval = 2 * numRows - 2
   
    for i in range(numRows) :
 
        j = 0
 
        while i+j < n :
 
            ans += s[i+j]
 
            if i != 0 and i != numRows - 1 and j+interval-i < n :
                ans += s[j+interval-i]
                
            j += interval
 
    return ans

Complexity Analysis

•Time Complexity: O(n), where n == len(s). Each index is visited once.

•Space Complexity: O(n). For the cpp implementation, O(1) if return string is not considered extra space.

Source :

https://leetcode.com/problems/zigzag-conversion/