Solution for ZigZag Conversion


  • 0
    B

    Approach this problem by observing the pattern.
    First of all check whether how many character difference is there when we have to print each row.

    If we have to print first and last row we just need to consider one difference. In the example given in the statement "PAYPALISHIRING" and 3 rows. We need to check the difference and that can be calculated as (n-1)th odd number that is (2*n-3).
    That means to print 1st and last row we need to print every (2n-3 + 1)th character.

    And for the rest of the rows we need to consider two difference : one from up and one from down .
    Hence we can divide this into two parts :
    1st part : Check differences of 1st and last row
    2nd part : Check differences of the rows left.

    Now to calculate the second part we need to check for 2 difference.
    If you observe the pattern as we go down difference is decreasing by 2 and for up we need to increase the difference by 2.
    Starting with the (n-1)th odd number we decrease 2 and increase the other difference by 2 and check for even and odd and print the difference.
    Here is the java code for the same.

    class Solution {
        public String convert(String s, int numRows) {
            // dividing problem into 2 parts : 
            // 1st part calculate 1st and last row as difference is going to be same
            // for rest of the rows we apply nested for 1 to n-1 as there are 2 differences to be considered
            // calculate (n-1)th odd number for calculating difference between 1st row character
            // corner cases
            if(numRows == 1){
                return s;
            }
            String output = new String("");
            int oddNum = 2 * numRows - 3;
            int len = s.length();
            // print 1st row
            for(int i = 0; i<len ; i += oddNum + 1 ){
                output += s.charAt(i);
            }
            
            int firstD = oddNum - 2;
            int secondD = 1;
            for(int i = 1; i < numRows - 1; i++){
                 firstD = oddNum - 2 * i;
                 secondD = 2 * i - 1;
                 int j = i;
                 int ct = 0 ;
                 int difference = 0;
                 while (j < len){
                     output += s.charAt(j);
                     difference = ct % 2 == 0 ? firstD : secondD ;
                     j += difference + 1;
                     ct += 1;
                 }
            }
            
            // print last row
            for(int i = numRows - 1; i<len ; i += oddNum + 1 ){
                output += s.charAt(i);
            }
            return output;
        }
    }
    

Log in to reply
 

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