ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

First lets understand the problem: here are a few examples:
nRows = 2
0 2 4 6 …
1 3 5 7
nRows = 3
0 4 8 …
1 3 5 7 9
2 6 10
nRows = 4
0 6 12 …
1 5 7 11
2 4 8 10
3 9

The number above is the index in the input string.
Then the idea becomes clear:

First we separate the string into “zig”s, in the above example nRows = 4, zigs are 0 ~5, 6 ~11 and so on.
Then we scan through the rows, and when scanning each row, we scan zigs from left to right. For each zig, first and last line has only one char and everything in between has 2 chars.
See the below code for reference, notice the outer loop is for every row and inner loop is for every zig.

public class Solution {
    public String convert(String s, int nRows) {
        if (nRows < 2)
            return s;
        int zigSize = (nRows - 1)*2;
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < nRows; i++) { // every row as outter loop
            for (int zig = 0; zig < (s.length()-1)/zigSize + 1; zig ++) { // every zig as inner loop
                if ((i == 0)) {//first has only one element each zig
                    result.append(s.charAt(zig*zigSize));
                }
                else if ( i == nRows - 1) {//last row also only have one element
                    if (zig*zigSize + nRows - 1 < s.length())
                        result.append(s.charAt(zig*zigSize + nRows - 1));
                    else
                        break;
                }
                else {
                    if(zig*zigSize + i < s.length())
                        result.append(s.charAt(zig*zigSize + i));
                    if(zig*zigSize + zigSize - i < s.length())
                        result.append(s.charAt(zig*zigSize + zigSize - i));
                }
            }
        }
        return new String(result);
    }
}

The idea is simply cut the string to trunk of size 2*nRows – 2, then iterate through the whole string to get the result. Notice the first and last line has only one char, the intermediate lines have 2 char (if exsit).

public class Solution {
    public String convert(String s, int nRows) {
        if (nRows == 1 || nRows >= s.length())
            return s;
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < nRows; i++) {
            //first line
            if (i == 0)
                for (int j = 0; j < s.length(); j += 2*nRows - 2) {
                    if (j+i < s.length())
                        result.append(s.charAt(j + i));
                }
            //last line
            else if (i == nRows - 1)
                for (int j = 0 ; j < s.length(); j += 2*nRows - 2) {
                    if (j+i < s.length())
                        result.append(s.charAt(j + i));
                }
            // intermedia lines, add 2 chars
            else
                for (int j = 0; j < s.length(); j += 2*nRows - 2) {
                    if (j+i < s.length())
                        result.append(s.charAt(j + i));
                    if (j + 2*nRows -2 - i < s.length())
                        result.append(s.charAt(j + 2*nRows -2 - i));
                }
        }
        return new String(result);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s