ZigZag Conversion

Question

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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Tags

• String

Thought

Reference: https://discuss.leetcode.com/topic/34573/python-o-n-solution-in-96ms-99-43

Two solutions:

1. Naive Solution: Use the matrix to store each character. In the original matrix, each row represent a column. Finally transpose the matrix will obtain the result.
2. Advanced Solution: Add the string by calculating on the fly. Use the a list to represent the whole matrix, each element in the list represent a row in the result matrix. Pay attention to determining the direction of the pointer.

The first algorithm is straightforward but slow and it cannot pass the test because the time limit. While the second solution is very efficient.

Code

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        step = (numRows == 1) - 1  # 0 or -1  
        rows, idx = [''] * numRows, 0
        for c in s:
            rows[idx] += c
            if idx == 0 or idx == numRows-1: 
                step = -step  #change direction  
            idx += step
        return ''.join(rows)