all articles

leetcode war 6 - ZigZag Conversion

2016-09-27 @sunderls

leetCode

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.