LeetCode #6 - Zigzag Conversion

Hello, coding enthusiasts! 👋 Today, we’re going to unravel another challenging problem from LeetCode: “Zigzag Conversion”.

Problem Statement

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

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);

Constraints

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ‘,’ and ‘.’.
1 <= numRows <= 1000

Examples

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"

Analysis

Our task is to convert a given string into a zigzag pattern with a specified number of rows and then read the result line by line.

Approach

The most efficient approach to solve this problem is to use a list of strings to represent each row of the zigzag pattern. Here’s how it works:

Initialize a list of strings: Create a list of strings rows with a length equal to the minimum of numRows and the length of s.
Fill the rows: Iterate over s, adding each character to the correct row in rows. Use a variable curRow to keep track of the current row, and a variable direction to keep track of whether we’re moving up or down the rows.
Join the rows: Join the strings in rows together to form the final result.

Time Complexity

The time complexity for this approach is O(n), where n is the length of the string. This is because we’re iterating over s once.

Space Complexity

The space complexity is also O(n), as we’re storing the result in a list of strings.

Code

Here’s the Python and JavaScript code for this approach:

Python

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

        res = [''] * numRows
        index, step = 0, 1

        for char in s:
            res[index] += char
            if index == 0:
                step = 1
            elif index == numRows - 1:
                step = -1
            index += step

        return ''.join(res)

JavaScript

var convert = function(s, numRows) {
    if (numRows == 1 || numRows >= s.length) {
        return s;
    }

    let res = Array(numRows).fill('');
    let index = 0, step = 1;

    for (let char of s) {
        res[index] += char;
        if (index == 0) {
            step = 1;
        } else if (index == numRows - 1) {
            step = -1;
        }
        index += step;
    }

    return res.join('');
};

Conclusion

In this post, we tackled the “Zigzag Conversion” problem from LeetCode using a list of strings to represent the rows of the zigzag pattern. This solution has a time complexity of O(n) and a space complexity of O(n).

Happy coding 😄!

Learn More:

LeetCode #6 – Zigzag Conversion