6. Zigzag Conversion

Intuition

The problem requires us to convert a given string into a zigzag pattern across a specified number of rows and then read it line by line. The key intuition here is to understand the zigzag traversal, which involves moving downwards in the rows and then reversing direction to move upwards until we hit the top row again, forming a repeating pattern.

Approach

1. Edge Case Handling: If numRows is 1, the zigzag pattern is essentially the same as the original string, so we return the string as is.
2. Initialize Rows: Create a list of strings, one for each row. This will store characters of each row as we iterate through the string.
3. Traversal and Direction Control: Use an index to track the current row and a boolean flag to control the direction (downwards or upwards). Start at the top row and move downwards initially. Append each character to the corresponding row. When we reach the bottom row, reverse the direction to upwards, and vice versa when we reach the top row.
4. Combine Rows: Once all characters have been placed in their respective rows, concatenate all rows to form the final string.

Complexity

Time Complexity:

O(n) where n is the length of the string. Each character is visited once and placed in the appropriate row.

Space Complexity:

O(n) where n is the length of the string. We use additional space to store characters in each row.

Code

C++

#include 
#include 
class Solution {
public:
    std::string convert(std::string s, int numRows) {
        if (numRows == 1) return s;
        std::vector rows(std::min(numRows, int(s.size())));
        bool reverse = false;
        int index = 0;
        for (char c : s) {
            rows[index] += c;
            if (reverse) {
                index--;
            } else {
                index++;
            }
            if (index == 0 || index == numRows - 1) {
                reverse = !reverse;
            }}
        std::string output;
        for (const std::string& row : rows) {
            output += row;}
        return output;
    }};

Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        rows = ['' for _ in range(min(numRows, len(s)))]
        reverse = False
        index = 0
        for char in s:
            rows[index] += char
            if reverse:
                index -= 1
            else:
                index += 1
            if index == 0 or index == numRows - 1:
                reverse = not reverse
        return ''.join(rows)

Java

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        List rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++) {
            rows.add(new StringBuilder());}
        boolean reverse = false;
        int index = 0;
        for (char c : s.toCharArray()) {
            rows.get(index).append(c);
            if (reverse) {
                index--;
            } else {
                index++;
            }
            if (index == 0 || index == numRows - 1) {
                reverse = !reverse;
            }}
        StringBuilder output = new StringBuilder();
        for (StringBuilder row : rows) {
            output.append(row);}
        return output.toString();
    }}

JavaScript

var convert = function (s, numRows) {
    if (numRows === 1) return s
    let rows = []
    for (let i = 0; i < numRows; i++) {
        rows[i] = []}
    let reverse = false
    let index = 0
    for (let i = 0; i < s.length; i++) {
        console.log(s[i])
        rows[index].push(s[i])
        if (reverse) {
            index--
        } else {
            index++
        }
        if (index === 0 || index === numRows - 1) {
            reverse = !reverse
        }}
    let output = []
    for (let i = 0; i < numRows; i++) {
        output.push(rows[i].join(""))}
    return output.join("")
};