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); } }