ZigZag Conversion Problem

Difficulty: Medium

ZigZag Conversion: The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”

Example 2:

Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:
P I N
A L S I G
Y A H R
P I

Example 3:

Input: s = “A”, numRows = 1
Output: “A”

ZigZag Conversion Problem Solution

Problem solution in Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        delta = -1
        row = 0
        res = [[] for i in range(numRows)]
        for c in s:
            res[row].append(c)
            if row == 0 or row == numRows - 1:
                delta *= -1
            row += delta
        for i in range(len(res)):
            res[i] = ''.join(res[i])
        return ''.join(res)

Problem solution in Java

class Solution {
    public String convert(String s, int numRows) {
        if (s.length() == 0 || s.length() == 1 || numRows == 0 || numRows == 1)
            return s;
        int cols = (s.length()+numRows-1 -1)/(numRows - 1);
        
        String ans = "";
        int col = 0, row = 0;
        while (row < numRows){
            col = 0;
            while (col <= cols){
                if (col % 2 == 0){
                    if (col*(numRows - 1)+row < s.length())
                        ans += s.charAt(col*(numRows - 1)+row);
                }else{
                    if (col*(numRows - 1)+numRows - 1 - row < s.length())
                        ans += s.charAt(col*(numRows - 1)+numRows - 1 - row);
                }
                if (row == 0 || row == numRows -1)
                    col+=2;
                else col++;
            }
            row++;
        }
        return ans;
    }
}

Problem solution in C++

string convert(string s, int numRows)
{
    if(numRows == 1)
    {
        return s;
    }
    
    vector<vector<char>> v(numRows, vector<char>());
    
    int row = 0;
    int step = 0;
    
    for(int i = 0; i < s.length(); i++)
    {
        v[row].push_back(s[i]);
        
        if(row == 0)
        {
            step = 1;
        }
        else if(row == numRows - 1)
        {
            step = -1;
        }
        
        row += step;
    }
    
    string result;
    
    for(int i = 0; i < numRows; i++)
    {
        result.append(v[i].begin(), v[i].end());
    }
    
    return result;
}

Problem solution in C

char * convert(char * s, int numRows){
    char conv[1000];
    int i, j, m, n, x, y, gap;
    
    if (numRows == 1)
        return s;
    
    n = numRows - 1;
    m = strlen(s);
    x = 0;
    
    for (i = 0; i < numRows; i++) {
        for (y = i, j = 0; y < m; y += gap, j++) {
            conv[x++] = s[y];
            gap = (n - ((j+1)&1)*(i%n) - (j&1)*((n-i)%n)) << 1;
        }
    }
    
    memcpy(s, conv, m);
    
    return s;
}