Zigzag Conversion In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement:

Given a string s and an integer numRows, arrange the characters of the string in a zigzag pattern on a number of rows and then read the string line by line. The number of rows is given by numRows. You should return the string after the zigzag conversion, which means reading the characters row by row.

For example:

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

The zigzag pattern for this example would look like:

P   A   H   N
A P L S I I G
Y   I   R

Approach:

1. Initial Setup:
   • If numRows is 1 or if numRows is greater than or equal to the length of the string, there is no zigzag pattern, so we can directly return the string.
2. Traversal Pattern:
   • We need to create numRows rows.
   • We will traverse the string and place each character in the appropriate row.
   • For each character, the position of the row alternates in a “zigzag” pattern: down (from row 0 to row numRows-1) and then up (from row numRows-2 to row 1).
3. Construction of the Result:
   • After placing characters in their respective rows, concatenate the rows to form the final result.

Algorithm:

1. Initialize an array of numRows empty strings to represent the rows.
2. Iterate through the characters of the string and determine the current row based on a direction indicator (down or up).
3. Place each character in the appropriate row.
4. Finally, join all the rows to form the output string.

Time Complexity:

• Time complexity: O(n), where n is the length of the string s. We traverse the string once and place each character in a row.
• Space complexity: O(n), where n is the length of the string, as we store the characters in numRows rows.

---

Code Implementation:

C:

#include <stdio.h>
#include <string.h>

char* convert(char* s, int numRows) {
    if (numRows == 1 || numRows >= strlen(s)) {
        return s;
    }
    
    char* result = (char*)malloc(strlen(s) + 1);
    int index = 0;
    
    // Create an array to store rows
    char rows[numRows][strlen(s)];
    for (int i = 0; i < numRows; i++) {
        memset(rows[i], 0, sizeof(rows[i]));
    }

    int row = 0, direction = 1;
    for (int i = 0; i < strlen(s); i++) {
        rows[row][i] = s[i];
        
        if (row == 0) direction = 1;
        if (row == numRows - 1) direction = -1;
        
        row += direction;
    }
    
    // Concatenate all rows
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < strlen(s); j++) {
            if (rows[i][j] != 0) {
                result[index++] = rows[i][j];
            }
        }
    }
    result[index] = '\0';
    return result;
}

int main() {
    char* s = "PAYPALISHIRING";
    int numRows = 3;
    char* result = convert(s, numRows);
    printf("%s\n", result);
    free(result);
    return 0;
}

C++:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string convert(string s, int numRows) {
    if (numRows == 1 || numRows >= s.size()) return s;
    
    vector<string> rows(numRows);
    int currentRow = 0;
    bool goingDown = false;
    
    for (char c : s) {
        rows[currentRow] += c;
        if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
        currentRow += goingDown ? 1 : -1;
    }
    
    string result = "";
    for (string row : rows) {
        result += row;
    }
    return result;
}

int main() {
    string s = "PAYPALISHIRING";
    int numRows = 3;
    cout << convert(s, numRows) << endl;
    return 0;
}

Java:

public class ZigzagConversion {
    public static String convert(String s, int numRows) {
        if (numRows == 1 || numRows >= s.length()) return s;
        
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        
        int currentRow = 0;
        boolean goingDown = false;
        
        for (char c : s.toCharArray()) {
            rows[currentRow].append(c);
            if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
            currentRow += goingDown ? 1 : -1;
        }
        
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        int numRows = 3;
        System.out.println(convert(s, numRows));
    }
}

Python:

def convert(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s
    
    rows = [''] * numRows
    currentRow, goingDown = 0, False
    
    for c in s:
        rows[currentRow] += c
        if currentRow == 0 or currentRow == numRows - 1:
            goingDown = not goingDown
        currentRow += 1 if goingDown else -1
    
    return ''.join(rows)

# Example usage
s = "PAYPALISHIRING"
numRows = 3
print(convert(s, numRows))

C#:

using System;
using System.Text;

public class ZigzagConversion {
    public static string Convert(string s, int numRows) {
        if (numRows == 1 || numRows >= s.Length) return s;
        
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        
        int currentRow = 0;
        bool goingDown = false;
        
        foreach (char c in s) {
            rows[currentRow].Append(c);
            if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
            currentRow += goingDown ? 1 : -1;
        }
        
        StringBuilder result = new StringBuilder();
        foreach (var row in rows) {
            result.Append(row.ToString());
        }
        
        return result.ToString();
    }

    public static void Main() {
        string s = "PAYPALISHIRING";
        int numRows = 3;
        Console.WriteLine(Convert(s, numRows));
    }
}

JavaScript:

var convert = function(s, numRows) {
    if (numRows === 1 || numRows >= s.length) return s;
    
    let rows = Array(numRows).fill('');
    let currentRow = 0;
    let goingDown = false;
    
    for (let i = 0; i < s.length; i++) {
        rows[currentRow] += s[i];
        if (currentRow === 0 || currentRow === numRows - 1) goingDown = !goingDown;
        currentRow += goingDown ? 1 : -1;
    }
    
    return rows.join('');
};

// Example usage
let s = "PAYPALISHIRING";
let numRows = 3;
console.log(convert(s, numRows));