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”
Table of Contents
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;
}