MUYANG GUO / INDEX

LeetCode

Leetcode 6 ZigZag Conversion - Medium

·1 min read·#Leetcode

6. ZigZag Conversion - Medium

Go to Leetcode

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"
Solution : Math, Space O(N), Time O(N), each element is visited once. 
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # check:
        n = len(s)
        if n <= numRows or numRows == 1:
            return s
        
        res = ''
        sequence = numRows * 2 - 2
        
        for i in range(numRows):
            for j in range(i, n, sequence):
                res += s[j]
                # exclude first row and last row, fill the middle rows
                # cooresponding element index from j with sequence, offset
                if i != 0 and i != numRows - 1 and j + sequence - 2*i < n:
                    res += s[j + sequence - 2*i]    
        return res

Comments