One-pass solution in Java


  • 0
    J

    Build in one pass, skipping through the source string. For each row, the skips can be calculated, based on numRows and the row being generated.

    Initial skip value, for each row is (numRows - 1) * 2 - 2*row.

    So, for numRows == 4, row 0 initial value is 6, row 1 initial value is 4, etc.

    As we walk through each row, we "flip-flop" the skip value off the starting skip value.

    So, for numRows == 4:
    -- row 0 skip series is 6, 6, 6, 6, ... (first row)
    -- row 1 skip series is 4,2,4,2,4,2...
    -- row 2 skip series is 2,4,2,4,2,4...
    -- row 3 skip series is 6, 6, 6, 6 ... (last row)

    public class Solution {
        public String convert(String s, int numRows) {
            String converted = s;
            
            if ( numRows >= 2 ) {
                int length = s.length();
                char[] sco = new char[length];
                int scoIdx = 0;
                int skip = (numRows - 1) * 2; 
    
                // iterate rows, for each row, start at the right point, and skip through
                // the original string as appropriate for the numRows.
                for ( int r = 0; r < numRows; r++ ) {
                    int i = r;
                    int iSkip = skip - 2*r;  // initialize to first skip value
                    
                    if ( iSkip <= 0 ) iSkip = skip; // end case for the last iteration
                    
                    while ( i < length ) {
                        sco[scoIdx++] = s.charAt(i);
                        i += iSkip;
                        
                        // flip/flop iSkip between high/low or equal half-values
                        iSkip = iSkip < skip ? skip - iSkip : skip;
                    }
                }            
                
                converted = new String(sco);
            }
            
            return converted;
        }
    }
    

Log in to reply
 

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