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
Idea:
- Treat this as an elevator
- The letter trend is from the top to the bottom, and then from the bottom to the top as the elevator, so only need to build n(numRows) level strings elevator, each string represents a layer(level)
- every time to visit a layer(level) while loop through the String s, store that letter into visiting layer(level)
- merge all the layers to get the final answer
Solution:
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
if (numRows === 1) return s;
let levels = [];
for (let i = 0; i < numRows; i++) {
levels[i] = [];
}
let down = true;
const n = s.length;
let index = 0;
for (let i = 0; i < n; i++) {
if (down) {
let end = index >= numRows - 1;
if (end) down = false;
levels[index].push(s[i]);
index = end ? index - 1: index + 1;
} else {
let top = index <= 0;
if (top) down = true;
levels[index].push(s[i]);
index = top ? index + 1: index - 1;
}
}
let res = "";
for (let i = 0; i < numRows; i++) {
res += levels[i].join('');
}
return res;
};