Algorithm
Problem Name: 6. Zigzag Conversion
Problem Link: https://leetcode.com/problems/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"
Constraints:
1 <= s.length <= 1000sconsists of English letters (lower-case and upper-case),','and'.'.1 <= numRows <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char* convert(char* s, int numRows) {
int len;
int i, j, k = 0;
char *p;
int step, up;
if (!s || !*s || numRows == 1) return s;
len = strlen(s);
p = malloc((len + 1) * sizeof(char));
//assert(p);
step = (numRows - 1) * 2; // max span
for (i = 0; i < numRows; i ++) {
j = i; // first letter of each row
up = 1;
while (j < len) {
p[k ++] = s[j];
if (i == 0 || i == numRows - 1) {
j += step; // full span
} else if (up) {
j += step - i * 2; // full span - offset
up = 0;
} else {
j += i * 2; // offset
up = 1;
}
}
}
p[k] = 0;
return p;
}
Input
s = "PAYPALISHIRING", numRows = 4
Output
"PINALSIGYAHRPI"
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string convert(string s, int numRows) {
if(numRows == 1) return s;
vector < string>v(numRows, "");
int d = 1;
int row = 0;
for(auto c: s){
v[row].push_back(c);
row += d;
if(row == numRows - 1) d = -1;
if(row == 0) d = 1;
}
string res;
for(auto x: v) res.append(x);
return res;
}
};
Input
s = "PAYPALISHIRING", numRows = 3
Output
"PAHNAPLSIIGYIR"
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
List < StringBuilder> list = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
list.add(new StringBuilder());
}
int idx = 0;
boolean downDirection = false;
for (char c : s.toCharArray()) {
list.get(idx).append(c);
if (idx == 0 || idx == numRows - 1) {
downDirection = !downDirection;
}
idx += downDirection ? 1 : -1;
}
StringBuilder result = new StringBuilder();
for (StringBuilder sb : list) {
result.append(sb.toString());
}
return result.toString();
}
}
Input
s = "A", numRows = 1
Output
"A"
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const convert = function(s, numRows) {
if (numRows === 1) {
return s;
}
let output = "";
for (let i = 1; i < = numRows; i++) {
let j = i - 1;
let maxIncrement = 2 * numRows - 2;
let increment = 2 * numRows - 2 - 2 * j;
if (increment === 0) {
increment = maxIncrement;
} else {
increment = maxIncrement - increment;
}
for (j; j < s.length; j += increment) {
output += s[j];
if (maxIncrement !== increment) {
increment = maxIncrement - increment;
}
}
}
return output;
};
Input
s = "PAYPALISHIRING", numRows = 3
Output
"PAHNAPLSIIGYIR"
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def convert(self, s, numRows):
if numRows == 1 or numRows >= len(s): return s
row, direction, res = 0, -1, [""] * numRows
for char in s:
res[row] += char
if row == 0 or row == numRows - 1: direction *= -1
row += direction
return "".join(res)
Input
s = "PAYPALISHIRING", numRows = 4
Output
"PINALSIGYAHRPI"
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _006_ZigZagConversion
{
public string Convert(string s, int numRows)
{
if (numRows <= 1 || s.Length <= 1) { return s; }
var result = new char[s.Length];
var index = 0;
for (int i = 0; i < numRows; i++)
{
for (int j = 0; (numRows * 2 - 2) * j + i < s.Length; j++)
{
var originalIndex = (numRows * 2 - 2) * j + i;
result[index++] = s[originalIndex];
if (i == 0 || i == numRows - 1) { continue; }
originalIndex = originalIndex + (numRows * 2 - 2) - i * 2;
if (originalIndex < s.Length)
{
result[index++] = s[originalIndex];
}
}
}
return new string(result);
}
}
}
Input
s = "A", numRows = 1
Output
"A"