Efficient Java solution


  • 0
    D

    Included an efficient solution in Java that builds the final output string in by iterating through the characters numRows times and building the output by calculating the offsets by breaking the problem down so that we only look at a sliding window of k characters at a time. For example, with numRows = 4:

    P     | I    | N
    A   L | S  I | G
    Y A   | H R  |
    P     | I    |
    

    {P, I, N} = {0, 6, 12}
    {A, L, S, I, G} = {1, 5, 7, 11, 13}
    {Y, A, H, R} = {2, 4, 8, 10}
    {P, I} = {3, 9}

    public String convert(String s, int numRows) {
            if (numRows == 1) {
                return s;
            }
            
            char[] chars = s.toCharArray();
            int textLength = chars.length;
            
            StringBuilder sb = new StringBuilder();
            
            int width = numRows * 2 - 2;
            
            for (int row = 0, secondCharOffset = width; row < numRows; row++, secondCharOffset -= 2) {    
                boolean hasSecondChar = secondCharOffset > 0 && secondCharOffset < width;
                for (int offset = 0; offset < textLength; offset += width) {                
                    int index = offset + row;
                    if (index < textLength) {
                        sb.append(chars[index]);
                        
                        int secondCharIndex = index + secondCharOffset;
                        if (hasSecondChar && secondCharIndex < textLength) {                    
                            sb.append(chars[secondCharIndex]);
                        }
                    }
                }
            }
            
            return sb.toString();
        }
    

Log in to reply
 

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