Mathematical solution with complete explanation


  • 0
    M

    Hello everyone,
    Here is a simple mathematical approach.

    let's take a look at at the string "0123456789" with 3 rows.
    Correct zigzag is thus:

    0   4   8
    1 3 5 7 9
    2   6
    

    First, let's take a closer look at the complete columns only:

    0   4   8
    1   5   9
    2   6
    
    • notice that the number of indices between two chars in the same row is constant.
    • Let's call that constant number of indices spacesBetween and compute it.
      • spacesBetween= numRows * 2 - 2.
      • So with 3 rows as in this problem:
        spacesBetween = 3*2 - 2
        spacesBetween = 4
    • The character at column X in row Y of zigzag is the character of given string s at index = Y + X*spacesBetween.
      • 1st char of 1st row has index in string s = 0 + 0*4 = 0.
      • 2nd char of 2nd row has index in string s = 1 + 1*4 = 5.
      • 3rd char of 2nd row has index in string s = 1 * 2*4 = 9.

    We can now generate the complete columns matrix using the following code

     string zigzag;  // used to store result
    
        for (int rowNum = 0; rowNum < numRows; rowNum++){
             for (int col = 0; col*spaceBetween + rowNum < s.size(); col++)
                 zigzag += s[col*spaceBetween + rowNum];
                    
     return zigzag;   
    

    Now, Let's take a look at the entire zigzag but let's add more rows and a longer string to spot the pattern more clearly:

    0     6       12
    1   5 7    11 13
    2 4   8 10    14
    3     9       15
    
    • can we find a pattern for the chars that are in incomplete columns?
      • First and last row don't have characters in incomplete columns.
      • First, observe that there is max one character between two characters in complete columns.
      • Then, notice that the 5 on row 1 is 1 less than 6 and the 11 on row 1 is 1 less than 12.
      • similarly, the 4 on row 2 is 2 less than 6 and the 10 on row 2 is 2 less than 12.
    • It appears we have identified a pattern!

    Finally, let's put it all together !

        string convert(string s, int numRows) {
            
            if (numRows == 1)
                return s;  // simple base case!
    
            // now calculat spacesBetween
            int spacesBetween = 2*numRows - 2;
            
            // used to store response
            string zigzag;
            
            for (int rowNum = 0; rowNum < numRows; rowNum++){
                for (int col = 0; col * spacesBetween + rowNum < s.size(); col++){
                    
                    // add char from complete column
                    zigzag += s[col*spacesBetween + rowNum];
                    
                    // first and last row don't have chars in incomplete columns so we continue
                    if (rowNum == 0 || rowNum == numRows - 1)
                        continue;
                    
                    // calculate index of character from incomplete column by finding the index of the first char of the next 
                    // complete column and subtracting the rowNum from it, as dictated by the pattern we observed earlier.
                    int incompleteColumnCharIndex = (col + 1)*spacesBetween - rowNum;
                    
                    // check that the index is a valid index in s. not too small not too large!
                    if(incompleteColumnCharIndex > 0 && incompleteColumnCharIndex < s.size())
                        zigzag += s[incompleteColumnCharIndex];
    
                }
            
            }
         return zigzag;   
        } 
    

Log in to reply
 

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