119 lines
2.4 KiB
JavaScript
119 lines
2.4 KiB
JavaScript
/*
|
|
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
|
|
*/
|
|
|
|
const { assert } = require('../../util/js');
|
|
/**
|
|
* @param {string} s
|
|
* @param {number} numRows
|
|
* @return {string}
|
|
*/
|
|
const convert = (s, numRows) => {
|
|
const pattern = [];
|
|
let x = 0;
|
|
let y = 0;
|
|
let goingDown = true;
|
|
for(let i = 0; i < s.length; i++){
|
|
if (y === numRows && goingDown) {
|
|
y = numRows - 2;
|
|
x++;
|
|
goingDown = false;
|
|
}
|
|
if (y == -1 && !goingDown){
|
|
y = 1;
|
|
x++;
|
|
goingDown = true;
|
|
}
|
|
|
|
if (!pattern[x]){
|
|
pattern[x] = [];
|
|
}
|
|
pattern[x][y] = s[i];
|
|
if (goingDown){
|
|
y++;
|
|
} else {
|
|
y--;
|
|
}
|
|
}
|
|
|
|
let col = 0;
|
|
let output='';
|
|
let j = 0;
|
|
// Time complexity: O(n)
|
|
while (j < s.length) {
|
|
// Reset col counter to 0 if at the last col
|
|
if (col === pattern.length) {
|
|
col = 0;
|
|
}
|
|
// Remove empty cols from list then skip
|
|
if (!pattern[col] || pattern[col].length === 0){
|
|
pattern.splice(col, 1);
|
|
continue;
|
|
}
|
|
|
|
const char = pattern[col][0];
|
|
// Add character to output and increment char counter
|
|
// Don't increment if character is null
|
|
// char can be null since we were not adding elements in every index
|
|
if (char) {
|
|
output+=char;
|
|
j++;
|
|
}
|
|
pattern[col].shift();
|
|
col++;
|
|
}
|
|
return output;
|
|
};
|
|
|
|
let s, numRows;
|
|
/* Test Case 1
|
|
* Input s = "PAYPALISHIRING", numRows = 3
|
|
* Output: "PAHNAPLSIIGYIR"
|
|
*/
|
|
|
|
s = 'PAYPALISHIRING';
|
|
numRows = 3;
|
|
sol = 'PAHNAPLSIIGYIR';
|
|
assert(convert(s, numRows) == sol, 'Output: "PAHNAPLSIIGYIR"');
|
|
|
|
/* Test Case 2
|
|
* Input: s = "PAYPALISHIRING", numRows = 4
|
|
* Output: "PINALSIGYAHRPI"
|
|
*/
|
|
s = 'PAYPALISHIRING';
|
|
numRows = 4;
|
|
sol = 'PINALSIGYAHRPI';
|
|
assert(convert(s, numRows) == sol, 'Output: "PINALSIGYAHRPI"');
|
|
|
|
/* Test Case 3
|
|
* Input: s = "AB", numRows = 1
|
|
* Output: "AB"
|
|
*/
|
|
s = 'AB';
|
|
numRows = 1;
|
|
sol = 'AB';
|
|
assert(convert(s, numRows) == sol, 'Output: "AB"');
|