# Use step
# Consider the middle numbers.
# Time: O(n)
# Space: O(1)

class Solution:
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s):
            return s
        step = numRows * 2 - 2
        res = ""
        for i in range(numRows):
            for j in range(i, len(s), step):
                res += s[j]
                if 0 < i < numRows - 1 and j + step - 2 * i < len(s):
                    res += s[j + step - 2 * i]
        return res


if __name__ == "__main__":
    s = "PAYPALISHIRING"
    numRows = 3
    y = Solution()
    print(y.convert(s, numRows))
# Use step
# Consider the middle numbers.
# Time: O(n)
# Space: O(1)

class Solution:
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s):
            return s
        step = numRows * 2 - 2
        res = ""
        for i in range(numRows):
            for j in range(i, len(s), step):
                res += s[j]
                if 0 < i < numRows - 1 and j + step - 2 * i < len(s):
                    res += s[j + step - 2 * i]
        return res


if __name__ == "__main__":
    s = "PAYPALISHIRING"
    numRows = 3
    y = Solution()
    print(y.convert(s, numRows))
# Use step # Consider the middle numbers. # Time: O(n) # Space: O(1)