Java approach using "max value of skips".. Easy and fast! :)


  • 0
    K
    public String convert(String s, int numRows) {
        // edge cases
        if (s.length() <= numRows) { return s; }
        else if (numRows == 1) { return s; }
        
        int totalLength = s.length();
        StringBuilder builder = new StringBuilder(totalLength);
        // calculate largest skip (i.e. skips needed to get to "equivalent" spot in zig-zag formation)
        int biggestSkip = (numRows - 1) * 2;
    
        for (int i = numRows; i > 0; i--) {
            int current = numRows - i;   // calculate starting index
            int skip = (i - 1) * 2;      // calculate initial characters to skip
              
            while (current < totalLength) {
                builder.append(s.charAt(current));  // add current letter to final string
                
                // skip value of 0 is not allowed; force it to become max
                if (skip == 0) { skip = biggestSkip; }
                
                current += skip;            // skip to next character
                skip = biggestSkip - skip;  // update skip using value of biggestSkip
                                                // this is the key ingredient to the algorithm!
                                                // because it allows me to "flip flop" my skip values
            }
        }
        return builder.toString();
    }
    

Log in to reply
 

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