Java- quick O(n) w/ explanation


  • 4
    S

    The trick to solving this problem is pattern recognition. Using the original String of "PAYPALISHIRING" and a variable number of rows, you can begin to see a pattern evolve. Values in brackets are the respective indexes of the String, "Step" represents the index mutation taken each iteration with a comma separating alternating values:

    3 rows:

    P A H N <-(0,4,8...)Step=4
    APLSIIG <-(1,3,5...)Step=2
    Y I R   <-(2,6,10...)Step=4
    

    4 rows:

    P  I  N <-(0,6,12...)Step=6
    A LS IG <-(1,5,7...)Step=4,2
    YA HR   <-(2,4,8...)Step=2,4
    P  I    <-(3,9,15...)Step=6
    

    5 rows:

    P   H <-(0,8,16...)Step=8
    A  SI <-(1,7,9...)Step=6,2
    Y I R <-(2,6,10...)Step=4
    PL  IG<-(3,5,11...)Step=2,6
    A   N <-(4,12...)Step=8
    

    From this pattern you can deduce three things:

    1. The "original" step taken is equal to (numRows * 2) - 2. This is only not true when numRows = 1.
    2. The "first" step taken on each step decrements by 2 from the original step each iteration until it equals 0, at which point the original step is restored (i.e this is the last row). For example, 8->6->4->2->0(8). You can use the given row count starting at 0, i, to calculate this quickly using originalStep - (i * 2). This will only be untrue on the last step.
    3. The alternating steps can be calculated by taking the absolute value of the current step and subtracting the original step from it. For example using the second row of the "5 rows" example, abs(6-8) = 2, abs(2-8) = 6, and so forth.

    My solution:

        public String convert(String s, int numRows) {
            if(numRows < 2 || numRows >= s.length()) return s;
            StringBuilder sb = new StringBuilder(s.length());
            int origStep = numRows * 2 - 2;
            int step = origStep;
            for(int i = 0; i < numRows; i++){
                step = i == numRows - 1 ? origStep : origStep - i * 2;
                int curr = i;
                while(curr < s.length()){
                    sb.append(s.charAt(curr));
                    curr += step;
                    int temp = Math.abs(step - origStep);
                    step = temp == 0 ? origStep : temp; //First/last rows
                }
            }
            return sb.toString();
        }
    

Log in to reply
 

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