Zigzag Conversion Medium ​

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

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

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

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

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

Solution ​

def convert(s, numRows):
    if numRows == 1 or numRows >= len(s):
        return s
    
    result = [''] * numRows
    index, step = 0, 1
    
    for char in s:
        result[index] += char
        
        if index == 0:
            step = 1
        elif index == numRows - 1:
            step = -1
        
        index += step
    
    return ''.join(result)

public String convert(String s, int numRows) {
    if (numRows == 1 || numRows >= s.length()) {
        return s;
    }
    
    StringBuilder[] result = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) {
        result[i] = new StringBuilder();
    }
    
    int index = 0, step = 1;
    
    for (char c : s.toCharArray()) {
        result[index].append(c);
        
        if (index == 0) {
            step = 1;
        } else if (index == numRows - 1) {
            step = -1;
        }
        
        index += step;
    }
    
    StringBuilder finalResult = new StringBuilder();
    for (StringBuilder sb : result) {
        finalResult.append(sb);
    }
    
    return finalResult.toString();
}

function convert(s, numRows) {
    if (numRows === 1 || numRows >= s.length) {
        return s;
    }
    
    const result = new Array(numRows).fill('');
    let index = 0, step = 1;
    
    for (const char of s) {
        result[index] += char;
        
        if (index === 0) {
            step = 1;
        } else if (index === numRows - 1) {
            step = -1;
        }
        
        index += step;
    }
    
    return result.join('');
}

Notes ​

You are given a string s and an integer numRows. You need to convert the string into a zigzag pattern with numRows rows, and then read it line by line to get the final converted string.

Time and Space Complexity Analysis ​

The time complexity of the given solutions is O(n), where n is the length of the input string s, because we iterate through the string once.

The space complexity for all solutions is O(n) because we use an array of strings (or StringBuilder in Java) to store the converted rows. In the worst case, each character of the input string will be in its corresponding row.

Overall, these solutions provide an efficient way to convert the string into the zigzag pattern as required.