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;
};Dry Run
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'