My Java answer with O(1) space, O(n) time with explanation.


  • 2
    D

    The basic view of this problem is we jump several steps in original to get the character in sequence.

    The gap for first and last row is easy: 2k-2. But for rows between:

    row 1: gap1: 2k - 2 - 2, gap2: 2

    row 2: gap1: 2k - 2 - 4, gap2: 4

    ....

    So there is a pattern for the jump gaps:
    gap1: 2*(k - 1 - i)
    gap2: 2 * i

    Then we could just make sure for each row, we jump the gap1, gap2, gap1, gap2 ... etc to get next character. Be careful with the gap is 0. So we keep tracking of last position and make sure we move forward.

    public String convert(String s, int nRows) {
        //Special case
        if (nRows >= s.length() || nRows == 1) {
            return s;
        }
        
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < nRows; i++) {
            //Two gaps for the next character
            int gap1 = 2 * (nRows - 1 - i);
            int gap2 = 2 * i;
            
            int j = i;
            //Record the previous char position in original string
            int prevPos = 0;
            
            // Init buffer
            sb.append(s.charAt(j));
            
            while (j < s.length()) {
                prevPos = j;
                j += gap1;
                //gap1 is 0 when it is last row, do not add it twice
                if (j != prevPos && j < s.length()) {
                    sb.append(s.charAt(j));
                }
                prevPos = j;
                j += gap2;
                //gap2 is 0 when it is first row, do not add it twice
                if (j != prevPos && j < s.length()) {
                    sb.append(s.charAt(j));
                }
            }
        }
        
        return sb.toString();
    }

Log in to reply
 

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