Zigzag Conversion - LeetCode Solution in C++, Java, Python

1. Introduction

The "Zigzag Conversion" problem involves rearranging characters of a string into a zigzag pattern on a specified number of rows and then reading the characters row by row. This problem tests understanding of string manipulation and pattern recognition.

2. Problem

Given a string s and an integer numRows, write a function convert to rearrange s in a zigzag pattern across numRows rows and return the new string read row by row.

3. Solution in C++

string convert(string s, int numRows) {
    if (numRows == 1) return s;
    string result;
    int cycleLen = 2 * numRows - 2;

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

Explanation:

1. Handle the edge case where numRows is 1.

2. Calculate the cycle length (one down and up movement in the zigzag).

3. Traverse each row, adding characters to result.

4. Add characters at regular intervals, considering the zigzag pattern.

5. Return the resulting string.

4. Solution in Java

public String convert(String s, int numRows) {
    if (numRows == 1) return s;
    StringBuilder result = new StringBuilder();
    int cycleLen = 2 * numRows - 2;

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

Explanation:

1. Return s directly if numRows is 1.

2. Use a StringBuilder for efficient string concatenation.

3. Determine the cycle length and iterate through each row.

4. Append characters to result based on the zigzag pattern.

5. Convert StringBuilder to string and return.

5. 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)

Explanation:

1. Return s as is if numRows is 1 or greater than the length of s.

2. Create a list result to store strings for each row.

3. Use index to track the current row and step to determine the direction of traversal.

4. Iterate through s, appending characters to the appropriate row.

5. Switch direction at the top and bottom rows.

6. Join all rows to get the final string.