Simple Java solution 7ms beats 87% - Easy to understand pattern


  • 0
    H

    If you write out the string in the correct format for rows = 1, 2, 3, 4, 5 you will notice a pattern.

    The difference between each character and the next on a specific row, is jump = ((numRows - 1) * 2).

    For the first and last rows, we only need to jump for one character.

    For 0th row, we need chars at indexes: 0, jump, jump*2, jump*3, ....

    For the last row, we need chars at indexes: `(numRows-1), (numRows-1)

    • jump, (numRows-1) + jump*2, ...`.

    For the inner rows, we need to jump for two characters. The first character starting at i, and the second character starting at jump - i.

    For the inner rows i, we need chars at indexes: i, (jump - i), i + jump, (jump - i) + jump, i + jump*2, (jump - i) + jump*2, ...

    By noticing this pattern we can go through the rows until we reach past the end of the String's index, and then move onto the next row. Once we go through all the rows we will have filled out the zigzag in order. Hope this helps.

    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        char[] str = s.toCharArray();
        int jump = (numRows - 1) * 2;
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < numRows; i++) {
            if(i == 0 || i == numRows - 1) {
                for(int j = i; j < str.length; j += jump) {
                    result.append(str[j]);
                } 
            } else {
                for(int j = i, k = jump - i; j < str.length; j += jump, k += jump) {
                    result.append(str[j]);
                    if(k < str.length) result.append(str[k]);
                }
            }
        }
        return result.toString();
    }

Log in to reply
 

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