Zigzag Conversion Problem and Solution

1. Introduction

The "Zigzag Conversion" problem involves rearranging the characters of a string into a zigzag pattern on a given number of rows and then reading the characters line by line. The challenge lies in computing the position of each character in the zigzagged output efficiently.

2. Solution in C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string convert(string s, int numRows) {
    if (numRows == 1) return s;

    string result;
    int n = s.size();
    int cycleLen = 2 * numRows - 2;

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j + i < n; j += cycleLen) {
            result += s[j + i];
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                result += s[j + cycleLen - i];
        }
    }
    return result;
}

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

Output:

Converted: PAHNAPLSIIGYIR

Explanation:

1. The function convert rearranges a string s into a zigzag pattern with numRows.

2. It calculates the cycle length based on the number of rows.

3. The string is traversed row by row, appending characters to the result.

4. Additional characters are added from the zigzag middle section when appropriate.

5. The result is the zigzag pattern read line by line.

3. Solution in Java

public class ZigzagConversion {
    public static String convert(String s, int numRows) {
        if (numRows == 1) return s;

        StringBuilder result = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                result.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    result.append(s.charAt(j + cycleLen - i));
            }
        }
        return result.toString();
    }

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

Output:

Converted: PAHNAPLSIIGYIR

Explanation:

1. The Java solution follows the same logic as the C++ solution.

2. A StringBuilder is used for efficient string concatenation.

3. The function traverses the string and constructs the zigzag pattern.

4. It returns the zigzag pattern read line by line as a string.

4. Solution in Python

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)

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

Output:

Converted: PAHNAPLSIIGYIR

Explanation:

1. The Python solution uses an array of strings to represent each row.

2. It iterates through each character in s, appending it to the correct row.

3. The direction of iteration (up or down the rows) is reversed at the top and bottom rows.

4. The final zigzag pattern is obtained by joining the strings of each row.