[tabby title=”Task”]
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"
This problem was taken from Leet code, ZigZag conversion
[tabby title=”Solution”]
It’s take the first example string: “PAYPALISHIRING”
An array representation of the string would be done by pushing each character into the array.
Then if we want to iterate through this array in zig zag pattern with 3 rows, it will look like this:
Then, we have to create 3 arrays representing the 3 rows as follows:
Dots represent empty strings which we have to ignore before concatenating all 3 rows, convert them to string and this is the answer to this problem.
But how to create the loop to traverse through the zig zag pattern (figure 1) ?
- first we set up `headingDown` flag to determine if we are going down or up
- each time when the
rowreachesnumRowswe are flipping the value ofheadingDown - when
headingDownis false (meaning that we are heading up) we have to do it diagonally: row — , col ++ - when
rowbecome0we are flipping againheadingDownand it becomes true again: row ++ and we keep storing values of every character we traversed in theresultarray.
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
// if we don't have any rows or there is an empty string just return back empty string
if(s.length === 0 || numRows === 0)
return '';
// if rows are numRows is just one, we return the same string
if(numRows === 1) {
return s;
}
var l = s.length;
// put the string into single dimension array to iterate through
var arr = s.split('');
var rowsArray = [];
var row = 0;
var col = 0;
var headingDown = true; // this determines if the cursor is heading down in the same column, or up leaping to the next column (dizgonal)
// instantiate numRows arrays to store values of each row
for(var i = 0; i < numRows; i ++) {
rowsArray[i] = [];
}
// loop through each element in arr and fill rowsArray ()
for(var i = 0; i < l; i ++) {
rowsArray[row][col] = arr[i];
if(headingDown) {
row ++;
}
else {
row --;
col ++;
}
if(row == numRows -1) {
headingDown = false;
} else if(row == 0) {
headingDown = true;
}
}
// Read 2D array and assemble the string
var result = [];
for(var i = 0; i < numRows; i ++) {
for(var j = 0; j < rowsArray[i].length; j ++) {
if(typeof rowsArray[i][j] != 'undefined') {
result.push(rowsArray[i][j]);
}
}
}
return result.join('');
};
convert('PAYPALISHIRING', 3);
convert('AB', 1);
//convert('ABC', 1);
How can we optimize this ?
the above example is good to read but not a good practical example. First we don’t need two dimensional array to store characters for each row. We could replace this with string array and just keep adding characters till we reached the end of the string. This way we also don’t need to keep track of cols
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
// if we don't have any rows or there is an empty string just return back empty string
if(s.length === 0 || numRows === 0)
return '';
// if rows are numRows is just one, we return the same string
if(numRows === 1) {
return s;
}
var l = s.length;
// put the string into single dimension array to iterate through
var arr = s.split('');
var left = 0;
var arrStrings = [];
var row = 0;
var col = 0;
var headingDown = true; // this determines if the cursor is heading down in the same column, or up leaping to the next column (dizgonal)
// instantiate numRows arrays to store values of each row
for(var i = 0; i < numRows; i ++) {
arrStrings[i] = '';
}
// loop through each element in arr and fill arrStrings ()
for(var i = 0; i < l; i ++) {
//arrStrings[row][col] = arr[i];
if(headingDown) {
arrStrings[row] += arr[i];
row ++;
}
else {
arrStrings[row] += arr[i];
row --;
col ++;
}
if(row == numRows -1) {
headingDown = false;
} else if(row == 0) {
headingDown = true;
}
}
var result = '';
// combine all strings and return as one
for(var i = 0; i < numRows; i ++) {
result += arrStrings[i];
}
return result;
};
[tabbyending]
Input:
Input:
Input:
