# 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:

1. 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`.
2. 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.
3. 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

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

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 ðŸ˜„!