6.Zigzag_Conversion(Medium).md

6. Zigzag Conversion (Medium)

Date and Time: Jul 9, 2024, 20:38 (EST)

Link: https://leetcode.com/problems/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 s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

P   A   H   N
A P L S I I G
Y   I   R

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4

Output: "PINALSIGYAHRPI"

P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1

Output: "A"

Constraints:

• 1 <= s.length <= 1000

• s consists of English letters (lower-case and upper-case), ',' and '.'.

• 1 <= numRows <= 1000

Walk-through:

Example 1
0  P   A   H   N
1  A P L S I I G
2  Y   I   R

Example 1: when numRows = 3,
row0: P->A = (3 - 1) * 2 = 4,
row1: A->L = (3 - 1) * 2 = 4,
A->P = (3 - 1) * 2 - (2 * 1) = 2 (First calculate distance from A->L, going back r = 1 to A, from A going back r = 1 to P, this is how we calculate A->P)

Example 2
0  P     I    N
1  A   L S  I G
2  Y A   H R
3  P     I

Example 2: when numRows = 4,
row0: P->I = (4 - 1) * 2 = 6,
row1: A->S = (4 - 1) * 2 = 6, A->L = (4 - 1) * 2 - (2 * 1) = 4

1. We need to have total numRows rows in ZigZag format. We observe that the interval between two columns on the same row is (numRows - 1) * 2, because of the V shape in ZigZag, we need to go down and go up, and we only have numRows - 1 rows available to go down, after we reach the bottom row, we only have numRows - 1 rows to go up, so we need to skip (numRows - 1) * 2 chars to get next char on the same row.

2. Notice that except the first row and the last row, we will have extra char in each interval between two normal columns. The way we get to this char is by removing r (current row) chars twice (up and down), just like how we go back from the another column and start going back to the first r chars, and going diagnoally for another r chars, we will get the extra char. So the formula is (numRows - 1) * 2 - (r * 2).

3. If numRows = 1, that means we only need to return s, since there is only one way to return s in one row (just s itself).

My Solution:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # (numRows - 1) * 2 to get another normal column for each row
        # Except the first and the last row, it takes (numRows - 2) * 2 - (r * 2) to get the extra char

        # TC: O(n), n = len(s), SC: O(n)
        res = ""
        interval = (numRows - 1) * 2
        # Edge case, if only 1 row, return s
        if numRows == 1:
            return s
        # Handle row by row
        for r in range(numRows):
            i = r
            while i < len(s):
                res += s[i]
                # Add extra char for non-first and non-last row
                if r > 0 and r < numRows - 1:
                    extraIndex = i + (interval - (r * 2))
                    # Check extraIndex is inbound
                    if extraIndex < len(s):
                        res += s[extraIndex]
                i += interval
        return res

Time Complexity: $O(n)$, n == len(s), because we traverse each char in s.
Space Complexity: $O(n)$, create a string with length n.

Slightly Convenience solution:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 1. Normal distance between two columns: (numRows - 1) * 2
        # 2. (numRows - 1) * 2 - (r * 2)

        # TC: O(n), n = len(s), SC: O(n)
        if numRows == 1:
            return s
        res = ""
        interval = (numRows - 1) * 2
        for row in range(numRows):
            l = row
            while l < len(s):
                res += s[l]
                l += interval
                # Rows we need to add extra chars, get the index of extra char
                extra = l - (row * 2)
                if row > 0 and row < numRows - 1 and extra < len(s):
                    res += s[extra]
        return res