ZigZag Conversion

6.ZigZag Conversion

String

Simulation

Problem Statement:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"

Example:

Input:

s = "PAYPALISHIRING", numRows = 3

→

Output:

"PAHNAPLSIIGYIR"

Algorithm:

1. Create StringBuilder for each row
2. Move down filling each row
3. Move up diagonally filling middle rows
4. Join all rows at the end

Complexity:

Time: O(n) | Space: O(n)

Java Solution:

public String convert(String s, int numRows) {
    // Create list of StringBuilders for each row
    List rows = new ArrayList<>();
    
    for (int i = 0; i < numRows; i++) {
        rows.add(new StringBuilder());
    }
    
    int index = 0;
    
    // Process string character by character
    while (index < s.length()) {
        // Move down
        for (int i = 0; i < numRows && index < s.length(); i++) {
            StringBuilder curr = rows.get(i);
            char letter = s.charAt(index);
            curr.append(letter);
            index++;
        }
        
        // Move up diagonally
        for (int i = rows.size() - 2; i > 0 && index < s.length(); i--) {
            StringBuilder curr = rows.get(i);
            char letter = s.charAt(index);
            curr.append(letter);
            index++;
        }
    }
    
    // Join all rows together
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < rows.size(); i++) {
        result.append(rows.get(i).toString());
    }
    
    return result.toString();
}

Python Solution:

def convert(self, s: str, numRows: int) -> str:
    if numRows == 1:
        return s
        
    # Initialize rows
    rows = [[] for _ in range(numRows)]
    index = 0
    
    while index < len(s):
        # Move down
        for i in range(numRows) and index < len(s):
            rows[i].append(s[index])
            index += 1
            
        # Move up diagonally
        for i in range(numRows-2, 0, -1) and index < len(s):
            rows[i].append(s[index])
            index += 1
            
    return ''.join(''.join(row) for row in rows)

C++ Solution:

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        
        vector rows(numRows);
        int index = 0;
        
        while(index < s.length()) {
            // Move down
            for(int i = 0; i < numRows && index < s.length(); i++) {
                rows[i] += s[index++];
            }
            
            // Move up diagonally
            for(int i = numRows-2; i > 0 && index < s.length(); i--) {
                rows[i] += s[index++];
            }
        }
        
        string result;
        for(const string& row : rows) {
            result += row;
        }
        
        return result;
    }
};