Java solution - Using StringBuffer and an assisting array


  • 0
    C

    If we read the characters in zigzag way, we will find the row numbers periodically
    repeat. For rownumber > 1, the period is (rownumber-1)*2. For example, if rownumber = 6, s = "PAYPALISHIRINGAROUNDTHEWORLD", the pattern is

    0  P         R         H
    1  A       I I       T E
    2  Y     H   N     D   W   
    3  P   S     G   N     O
    4  A I       A O       R D
    5  L         R         L
    

    The row numbers repeat as "0 1 2 3 4 5 4 3 2 1", with length equal to 10 (= 5*2). It's not hard for us to find the repeated pattern, which starts from 0 to n-1 and then decreases to 1.
    So, we can use a StringBuffer array sb to represent each line's string and read through the string and append the character to sb[0], sb[1], ..., sb[n-1], sb[n-2], ... sb[1] periodically. Meanwhile, an array is used to indicate which StringBuffer we shoud append to.
    Here is the solution:

    public class Solution {
        public String convert(String s, int numRows) {
            if (numRows == 1) return s;
            StringBuffer[] sb = new StringBuffer[numRows];
            // init sb
            for (int i = 0; i < numRows; i++) {
                sb[i] = new StringBuffer();
            }
            
            int period = (numRows-1)*2;
            int[] index = new int[period];
            // init index
            for (int i = 0; i <= period/2; i++) {
                index[i] = i;
            }
            for (int i = period-1, j = 1; i > period/2; i--) {
                index[i] = j++;
            }
    
            
            for (int i = 0; i < s.length(); i++) {
                sb[index[i%period]].append(s.charAt(i));
            }
            
            StringBuffer res = new StringBuffer();
            for (int i = 0; i < numRows; i++) {
                res = res.append(sb[i]);
            }
            
            return res.toString();
        }
    }
    

Log in to reply
 

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