Solution with StringBuilder array

  • 0

    Idea is as follows. For the zig-zag below:

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

    Process a half-zig one at a time. In the above example, there are 4 half-zigs as shown below:

    1st:       2nd:        3rd:        4th:
    P          A           H           N
    A P        L S         I I         G
    Y          I           R

    1-3 are called a complete half-zig, while the 4th one is incomplete.

    The idea is to convert all half-zigs from left to right into a StringBuilder array. After that, combine StringBuilder array into a single string.

    Code in Java:

    public String convert(String s, int numRows) {
        if(s.length()<=1 || numRows<=1) return s;
        StringBuilder[] sb = new StringBuilder[numRows]; // sb stores all of substrings of every layer
        for (int i = 0; i < sb.length; i++) 
            sb[i] = new StringBuilder("");
        int L = s.length();
        int len = (numRows<<1) - 2; // lenth of a half-zig
        int count = L/len; // total number of complete half-zigs
        for(int i=1; i<=count+1; i++) {
            int start = len*(i-1); // starting index
            for(int r=0; r<len && start+r<L; r++) {
                if(r<numRows) sb[r].append(s.charAt(start+r));
                else sb[len-r].append(s.charAt(start+r));
        for(int r=1; r<numRows; r++)
            sb[0].append(sb[r]); // combine all sb items
        return sb[0].toString();

Log in to reply

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