6. Zigzag Conversion

Problem Description

The problem asks to convert a given string into a zigzag pattern with a specified number of rows and then read the string line by line. For example, converting "PAYPALISHIRING" with 3 rows results in "PAHNAPLSIIGYIR".

Solution Approaches and Code

This problem can be solved efficiently using two main approaches:

Approach 1: Simulation

This approach directly simulates the zigzag pattern. We use an array of strings (or lists) to represent the rows of the zigzag pattern. We iterate through the input string and add each character to the appropriate row, changing the row index as we move up and down the zigzag.

Time Complexity: O(n), where n is the length of the input string. We iterate through the string once. Space Complexity: O(n), in the worst case (numRows = 1) to store the converted string. The intermediate array for rows also uses O(n) space in the worst case.

Code (Python):

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
 
        rows = [[] for _ in range(numRows)]
        row_index = 0
        direction = 1  # 1 for down, -1 for up
 
        for char in s:
            rows[row_index].append(char)
            row_index += direction
 
            if row_index == numRows - 1 or row_index == 0:
                direction *= -1
 
        result = "".join(["".join(row) for row in rows])
        return result
 

Approach 2: Pattern Identification

This approach analyzes the pattern of how characters are placed in the zigzag. Characters on the first and last rows appear at regular intervals. Characters on the intermediate rows appear in pairs with a specific pattern in their intervals. By identifying this pattern, we can construct the converted string more directly without simulating the pattern explicitly.

Time Complexity: O(n), where n is the length of the input string. We still iterate through the string once.

Space Complexity: O(n), primarily for storing the result string.

Code (Python):

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
 
        result = ""
        cycle_len = 2 * numRows - 2  # Length of one zigzag cycle
 
        for i in range(numRows):
            for j in range(i, len(s), cycle_len):
                result += s[j]
                if i > 0 and i < numRows - 1 and j + cycle_len - 2 * i < len(s):
                    result += s[j + cycle_len - 2 * i]
        return result
 

Other Languages:

The above approaches can be implemented in other languages like Java, C++, JavaScript, etc. The core logic remains the same, with only minor syntactic differences. For example, a Java implementation of Approach 1:

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || numRows >= s.length()) return s;
 
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) rows.add(new StringBuilder());
 
        int row_index = 0;
        int direction = 1;
 
        for (char c : s.toCharArray()) {
            rows.get(row_index).append(c);
            row_index += direction;
            if (row_index == numRows - 1 || row_index == 0) direction *= -1;
        }
 
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) result.append(row);
        return result.toString();
    }
}

Both approaches offer the same time complexity. The choice between them might depend on personal preference or slight performance variations depending on the specific programming language and its optimization strategies. Approach 1 might be slightly easier to understand for beginners, while Approach 2 is often considered more concise once the pattern is grasped.