0006-zigzag-conversion

Try it on leetcode

Description

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);

 

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"

 

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

Solution(Python)

from collections import defaultdict
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        #
        # 
        # "PAYPALISHIRING"
        #
        #  s , numRows=3
        #   
        #  trace the rwos
        #  0 1 2 1 0 1 2 1
        #  cyclcical
        #  pattern follows each cycle is detreminded by number of rows
        #  if m is number of rows
        #  0...m then m - 1,m-2....0 and cycle continues
        # 
        #  You iterate through the string and assign each character to a row
# Then you need to output all characters from row 0, then all from row 1, then all from row 2, etc.
# 
        if numRows == 1:
            return s
        row = 0
        direction = 1
        hashmap =  defaultdict(list)
        for i,char in enumerate(s):
            hashmap[row].append(char)
            
            next_row =  row + direction
            if next_row >= numRows  or next_row < 0:
                direction *= -1 
            row += direction
        
        result = ""

        for rows_idx in range(numRows):
            result += "".join(hashmap[rows_idx])
        return result