all articles

2016-09-27

# leetcode war :ZigZag Conversion

https://leetcode.com/problems/zigzag-conversion/

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 text, int nRows);``

`convert("PAYPALISHIRING", 3)` should return `"PAHNAPLSIIGYIR"`.

# Analysis

Let's take `"1234567890"` as an example, for a zigzag at rows of 3, we get

``````1 5 9
24680
3 7``````

for rows of 4, we get

``````1  7
2 68
35 9
4  0``````

maybe we can do this in two ways I think:

1. init a 2-d matrix, place the characters in the array, and collect them again. time cost: O(n) and space cost: O(n);
2. direct calculation , we find a f(x) which takes in old index and return a new index.

# Solution 1: using a Matrix

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

var rows = numRows;
var cols = 0;
// we take rows-2 lins as a block
var blockNum = Math.floor(length / (rows * 2 - 2));
var restNum = length % (rows * 2 - 2);
cols = blockNum * (rows - 1) +  (restNum > rows ? (1 + restNum - rows) : 1);

var map = [];
// init the matrix
for(var i = 0; i < rows; i++){
map.push([]);
}

// we use a direction flag, Dx & Dy to show which phase we are in
// {0, 1}: moving down
// {1, -1}: moving upright
var x = 0, y = -1, Dx = 0, Dy = 1;
for(var i = 0; i < length; i++){
x += Dx;
y += Dy;
map[y][x] = s[i];

if (y >= rows - 1){
Dy = -1;
Dx = 1;
}

if (y <= 0){
Dy = 1;
Dx = 0;
}
}

var result = [];
for (var i = 0; i < rows; i++){
for(var j = 0; j < cols; j++){
if (map[i][j]){
result.push(map[i][j]);
}
}
}
return result.join('');
};``````

while this seems right, but it cost too much time - Time Limit Exceeded.

The result map is actually sparse, we can compress it better. for example:

``````1  7
2 68
35 9
4  0``````

can be compressed to:

``````1 7
268
359
4 0``````

which leads to following solution:

# Solution 2: improved condensed matrix

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

var rows = numRows;
var cols = 0;
// we take rows-2 lins as a block
var blockNum = Math.floor(length / (rows * 2 - 2));
var restNum = length % (rows * 2 - 2);
cols = blockNum * 2 +  (restNum > rows ? 2 : 1);
var map = [];
// init the matrix
for(var i = 0; i < rows; i++){
map.push([]);
}

// we use a direction flag, Dx & Dy to show which phase we are in
// {0, 1}: moving down
// {1, -1}: moving upright
var x = 0, y = -1, Dy = 1;
for(var i = 0; i < length; i++){
y += Dy;
map[y][x] = s[i];
if (y >= rows - 1){
Dy = -1;
x += 1;
}

if (y === 1 && Dy === -1){
x += 1;
}

if (y <= 0){
Dy = 1;
}

}
var result = [];
for (var i = 0; i < rows; i++){
for(var j = 0; j < cols; j++){
if (map[i][j]){
result.push(map[i][j]);
}
}
}
return result.join('');
};``````

which is now accepted by leetcode, 215ms which is very slow ranking last 20% of all accepted solutions. There must be better solution.

from above solution, we can omit the process of lining up and collecting, we just do the direct calculation:

# solution 3: direction calculation

Look more at our map: for rows of 3:

``````1 5 9
24680
3 7``````

for rows of 4:

``````1 7
268
359
4 0``````

we can see that rows are actually following indices:

``````0, (rows - 1) * 2, (rows - 1) * 4 ...
1, (rows - 1) * 2 - 1, (rows - 1) * 2 + 1, (rows - 1) * 4 - 1, (rows - 1) * 4 + 1 ...
2, (rows - 1) * 2 - 2, (rows - 1) * 2 + 2, (rows - 1) * 4 - 2, (rows - 1) * 4 + 2 ...
rows - 1, (rows - 1) * 2 + rows - 1,  (rows - 1) * 4 + rows - 1 ...``````

This leads us to following algorithm:

``````var convert = function(s, numRows) {
var length = s.length;

if (length <= numRows || numRows === 1){
return s;
}

var result = [];
var j = 0;
var step = numRows - 1;

for (var i = 0; i < numRows; i++){
if(i === 0 || i === numRows - 1){
j = i;
while(j < length){
result.push(s[j]);
j += step * 2;
}
} else {
result.push(s[i]);
j = step * 2;
while(j - i < length){
if(j - i < length && j - i > i){
result.push(s[j - i]);
}

if (j + i < length){
result.push(s[j + i]);
}
j += step * 2;
}
}
}
return result.join('');
};
``````

OK, this time it went to top 25% of accepted solutions with 145ms. 