## DEV Community

Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

# LeetCode - ZigZag Conversion

### Problem statement

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);
``````

Problem statement taken from: https://leetcode.com/problems/zigzag-conversion

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 <= 1000
- s consists of English letters (lower-case and upper-case), ',' and '.'
- 1 <= numRows <= 1000
``````

### Explanation

#### Process by row

The number of rows into which the string should be zig-zag is passed. We can create an array of strings. Based on the current index, append that character in the respective string array index.

Let's check the algorithm.

``````- if numRows <= 1
- return s

- initialize i, set row = 0, down = true

- initialize array of strings: string array[numRows]

- loop for i = 0; i < numRows; i++
- set array[i] = "" (empty string)

- loop for i = 0; i < s.size(); i++
- append character to string
array[row] += s[i];

- if row == 0
- set down = true

- if row == numRows - 1
- set down = false

- increment or decrement row based on down boolean
down ? row++ : row--

- set string answer = ""

- loop for i = 0; i < numRows; i++
- answer += array[i]

- return answer
``````

#### C++ solution

``````class Solution {
public:
string convert(string s, int numRows) {
if(numRows <= 1) {
return s;
}

int i, row = 0;
bool down = true;
string array[numRows];

for(i = 0; i < numRows; i++){
array[i] = "";
}

for(i = 0; i < s.size(); i++){
array[row] += s[i];

if(row == 0){
down = true;
}

if(row == numRows - 1){
down = false;
}

down ? row++ : row--;
}

string answer = "";

for(i = 0; i < numRows; i++){
answer += array[i];
}

return answer;
}
};
``````

#### Golang solution

``````func convert(s string, numRows int) string {
if numRows <= 1 {
return s
}

i, row := 0, 0
down := true
array := make([]string, numRows)

for i = 0; i < len(s); i++ {
array[row] += string(s[i])

if row == 0 {
down = true
}

if row == numRows - 1 {
down = false
}

if down {
row++
} else {
row--
}
}

answer := ""

for i = 0; i < numRows; i++ {
answer += array[i]
}

return answer
}
``````

#### Javascript solution

``````var convert = function(s, numRows) {
if( numRows <= 1 ){
return s;
}

let i, row = 0;
let down = true;
let array = [];

for( i = 0; i < numRows; i++ ){
array[i] = "";
}

for( i = 0; i < s.length; i++ ){
array[row] += s[i];

if( row == 0 ){
down = true;
}

if( row == numRows - 1 ){
down = false;
}

down ? row++ : row--;
}

var answer = "";

for( i = 0; i < numRows; i++ ){
answer += array[i];
}

return answer;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: s = "ABCDEFGH", numRows = 3

Step 1: if numRows <= 1
3 <= 1
false

Step 2: int i, row = 0
bool down = true
string array[numRows]
string array[3];

Step 3: loop for i = 0; i < numRows; i++
- set array[i] = "";

numRows = 3
so array[0] = array[1] = array[2] = ""

Step 4: loop for i = 0; i < s.size()
i < 8
0 < 8
true

array[row] += s[i]
array[row] = array[0] + s[0]
= "" + "A"
= "A"
array[0] = "A"

row == 0
true
down = true

down ? row++ : row--
row++
row = 1

i++
i = 1

Step 5: loop for i < s.size()
i < 8
1 < 8
true

array[row] += s[i]
array[row] = array[1] + s[1]
= "" + "B"
= "B"
array[1] = "B"

row == 0
false

row == numRows - 1
1 == 2
false

down ? row++ : row--
row++
row = 2

i++
i = 2

Step 6: loop for i < s.size()
i < 8
2 < 8
true

array[row] += s[i]
array[row] = array[2] + s[2]
= "" + "C"
= "C"
array[2] = "C"

row == 0
false

row == numRows - 1
2 == 2
true
down = false

down ? row++ : row--
row--
row = 1

i++
i = 3

Step 7: loop for i < s.size()
i < 8
3 < 8
true

array[row] += s[i]
array[row] = array[1] + s[3]
= "B" + "D"
= "BD"
array[1] = "BD"

row == 0
false

row == numRows - 1
1 == 2
false

down ? row++ : row--
row--
row = 0

i++
i = 4

Step 8: loop for i < s.size()
i < 8
4 < 8
true

array[row] += s[i]
array[row] = array[0] + s[4]
= "A" + "E"
= "AE"
array[1] = "AR"

row == 0
true
down = true

row == numRows - 1
1 == 2
false

down ? row++ : row--
row++
row = 1

i++
i = 5

Step 9: loop for i < s.size()
i < 8
5 < 8
true

array[row] += s[i]
array[row] = array[1] + s[5]
= "BD" + "F"
= "BDF"
array[1] = "BDF"

row == 0
false

row == numRows - 1
1 == 2
false

down ? row++ : row--
row++
row = 2

i++
i = 6

Step 10: loop for i < s.size()
i < 8
6 < 8
true

array[row] += s[i]
array[row] = array[2] + s[6]
= "C" + "G"
= "CG"
array[2] = "CG"

row == 0
false

row == numRows - 1
2 == 2
true
down = false

down ? row++ : row--
row--
row = 1

i++
i = 7

Step 11: loop for i < s.size()
i < 8
7 < 8
true

array[row] += s[i]
array[row] = array[1] + s[7]
= "BDF" + "H"
= "BDFH"
array[1] = "BDFH"

row == 0
false

row == numRows - 1
1 == 2
false

down ? row++ : row--
row--
row = 0

i++
i = 8

Step 11: loop for i < s.size()
i < 8
8 < 8
false

Step 12: string answer = "";

Step 13: loop for( i = 0; i < numRows; i++ )
answer += array[i];

array[0] = "AE"
array[1] = "BDFH"
array[2] = "CG"

so answer is "AEBDFHCG"

Step 14: return answer

So the answer is "AEBDFHCG"
``````