[LeetCode] 6. Zigzag Conversion

1. 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"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

2. Thoughts

1. Make an array of strings.
2. In a zigzag manner, add each alphabet to the strings.
3. concat each string
   (Cautious of when to go down, and up for the zigzag)

3. Tips learned

4. My solution

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

        zigzag = ["" for i in range(numRows)]

        zig = numRows
        zag = numRows - 2
        for i in range(len(s) // (zig + zag) + 1):
            for j in range(zig):
                if i * (zig + zag) + j >= len(s):
                    break
                zigzag[j] += s[i * (zig + zag) + j]
            for j in range(zag):
                if i * (zig + zag) + zig + j >= len(s):
                    break
                zigzag[zag - j] += s[i * (zig + zag) + zig + j]

        result = ""

        for i in range(numRows):
            result += zigzag[i]

        return result

1157/1157 cases passed (51 ms)
Your runtime beats 84.42 % of python3 submissions
Your memory usage beats 16.59 % of python3 submissions (17.5 MB)

5. AI Solution and Improvements

Your solution for converting a string into a zigzag pattern is quite comprehensive, but it can be optimized for readability and efficiency. The key to optimizing this problem lies in understanding the pattern of indexes as they appear in the zigzag order. Here's an optimized version of your code:

1. Use a simpler iteration logic: The zigzag pattern can be visualized as a series of peaks and valleys. The characters at the peaks and valleys are located at intervals of (2 * numRows - 2) characters apart in the original string. The characters in between these peaks and valleys follow a specific pattern that can be calculated directly.

2. Avoid multiple loops: You can achieve the desired result with a single loop over the length of the string, which can improve readability and potentially performance.

Here is the revised code:

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

        result = [""] * numRows
        step, row = -1, 0

        for char in s:
            result[row] += char
            if row == 0 or row == numRows - 1:
                step = -step
            row += step

        return ''.join(result)

In this version:

• The result list is initialized with empty strings for each row.
• A step variable is used to move up or down the rows.
• The row variable keeps track of the current row.
• The loop iterates through each character in the string. The character is added to the appropriate row in result.
• When the top or bottom row is reached, step is reversed to change the direction.
• Finally, all rows are concatenated to form the final zigzag string.

This approach is more direct and makes it easier to understand the movement through the zigzag pattern.