O(n) and O(n) space. Good Explanation. Clear Code. Live Demo. Javascript


  • 0

    To understand this problem, just list few converted strings with different rows and you will notice the pattern:

    rows = 3
    
    P   A   H   N     step: 4
    A P L S I I G     step: 2
    Y   I   R         step: 4
    
    ------------------------------
    
    rows = 4
    
    P     I     N     step: 6
    A   L S   I G     step: 4, 2
    Y A   H R         step: 2, 4
    P     I           step: 6
    
    ------------------------------
    
    rows = 5
    
    P       H         step: 8
    A     S I         step: 6, 2
    Y   I   R         step: 4, 4
    P L     I G       step: 2, 6
    A       N         step: 8
    
    ------------------------------
    
    rows = 6
    
    P         R      step: 10
    A       I I      step: 8, 2 
    Y     H   N      step: 6, 4
    P   S     G      step: 4, 6
    A I              step: 2, 8
    L                step: 10
    
    ------------------------------
    
    rows = 7
    
    P       N       step: 12
    A     I G       step: 10, 2
    Y    R          step: 8, 4
    P   I           step: 6, 6
    A  H            step: 4, 8
    L S             step: 2, 10
    I               step: 12
    
    ------------------------------
    
    rows = 8
    
    P               step: 14
    A      G        step: 12, 2
    Y     N         step: 10, 4
    P    I          step: 8, 6
    A   N   R       step: 6, 8
    L  I            step: 4, 10
    I H             step: 2, 12
    S               step: 14
    

    Notice that we have origin step which is applied to the very first and very last rows only. It is always equal to 2*number of rows - 2.

    Then all other steps have their decrease by two starting from the origin - origin - 2*row. Of course, these rows have their flipped counterpart that should be applied on every odd step instead of the base one. They can be calculated as origin - base.

    So this is it. We just have a for loop that loops thru all row numbers and inside it, a while loop that starts from i and on every iteration adds a step value that is calculated according to this pattern rules (getStep function).

    Live Demo

    Entire code:

    var getStep = function getStep(rows, row, step) {
      var origin = 2*(rows-1);
      var base = (row === 0 || row === rows-1) ? origin : origin - 2*row;
      var flip = (row === 0 || row === rows-1) ? origin : origin - base;
      
      return (step % 2 === 0) ? base : flip;
    }
    
    var convert = function convert(str, rows) {
      if (rows <= 1 || rows > str.length) { return str; }
      
      var result = '';
      for (var i = 0; i < rows; i++) {
        
        var step = 0;
        var j = i;
        var rowResult = '';
        
        while (j < str.length) {
          rowResult += str[j];
          j += getStep(rows, i, step);
          step++;
        }
    
        result += rowResult;
      }
      return result;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.