Leetcode 6 Solution

This article provides solution to leetcode question 6 (zigzag-conversion)
Categories:
Tags:
Access this page by simply typing in "lcs 6" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/zigzag-conversion

Thinking Process

This question requires us to find out the pattern of the final string.

  • The chars of the first line of the zigzag locate at 2 * (n - 1) * k.
  • The chars of the second line of the zigzag locate at 1 + 2 * (n - 1) * k and 2 * (n - 1) - 1 + 2 * (n - 1) * k.
  • The chars of the third line of the zigzag locate at 2 + 2 * (n - 1) * k and 2 * (n - 1) - 2 + 2 * (n - 1) * k.
  • The chars of the fourth line of the zigzag locate at 3 + 2 * (n - 1) * k and 2 * (n - 1) - 3 + 2 * (n - 1) * k.
  • …
  • The chars of the last line of the zigzag locate at n - 1 + 2 * (n - 1) * k.

In all above cases, k iterate from 0 to a number where the index exceeds the size of the string.

Time & Space Complexity

Assuming N is the size of the array, the time & space compelxities are:

  • Time complexity: O(N)
  • Space complexity: O(N)

Solution

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        n = numRows

        if n == 1:
            return s

        res = ""

        # Append the first line.
        i = 0
        while i < len(s):
            res += s[i]
            i += 2 * (n - 1)

        # Append the middle lines.
        first_l = 1
        first_r = 2 * (n - 1) - 1

        while first_l < first_r:
            l = first_l
            r = first_r

            while l < len(s):
                res += s[l]
                if r < len(s):
                    res += s[r]
                l += 2 * (n - 1)
                r += 2 * (n - 1)

            first_l += 1
            first_r -= 1

        # Append the last line.
        i = n - 1
        while i < len(s):
            res += s[i]
            i += 2 * (n - 1)

        return res