6. Zigzag Conversion

Solution 1: 2D-Array + Simulation (模擬 Z 字形移動)

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        zigzagRow = numRows * [""]
        lenN = len(s)
        idxS = 0
        while idxS < lenN:
            # Vertically down
            rowIdx = 0
            while rowIdx < numRows and idxS < lenN:
                zigzagRow[rowIdx] += s[idxS]
                rowIdx += 1
                idxS += 1
            # Obliquely up
            rowIdx = numRows - 2
            while rowIdx >= 1 and idxS < lenN:
                zigzagRow[rowIdx] += s[idxS]
                rowIdx -= 1
                idxS += 1
        return ''.join(zigzagRow)

Time Complexity: O(N)
Space Complexity: O(N*Rows) // 2D String Array

Solution 2: Zigzag pattern (找出 1:1 映射規律)

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if 1 == numRows: 
            return s

        zigzag = ""
        # numRows = 4
        # ORIG: 0 1 2  3 4 5 6 7 8 9 10 11 12 13 14 15...
        #
        # ZigZ: 0   6     12
        #       1  57   1113 
        #       2 4 8 10  14
        #       3   9     15
        for rowIdx in range(numRows):
            idxOfCurrZigzagRow = rowIdx
            elmtCntOfCurrZigzagRow = 0
            while idxOfCurrZigzagRow < len(s):
                zigzag += s[idxOfCurrZigzagRow]
                
                isFirstRow = rowIdx == 0
                isEvenElmt = elmtCntOfCurrZigzagRow % 2 == 0
                isNotLastRow = rowIdx != numRows - 1
                # e.g, (rowIdx=1) 1 -> 5, 7 -> 11... 
                if (isFirstRow or isEvenElmt) and isNotLastRow:
                    idxOfCurrZigzagRow += 2*(numRows - 1 - rowIdx)
                # e.g, (rowIdx=1) 5 -> 7, 11 -> 13...
                else:
                    idxOfCurrZigzagRow += 2*rowIdx;
                    
                elmtCntOfCurrZigzagRow += 1 
        return zigzag

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/zigzag-conversion/discuss/3403/Easy-to-understand-Java-solution