Make

  • R = total required rows
  • d = R - 2 2 is contains head line and tail line that not need insert a character between two columns.
  • r = current row offset, which starts from 0.
  • c = current column offset, which starts from 0.

We can use a formula to make columns, which is \(c(R+d)+r\).

For example, "PAYPALISHIRING", numRows=3:

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

The columns only the head and tail rows is correct should be:

R=3,d=1

c=0 c=1 c=2 c=3 c=4
r=0 0 = 0(3+1)+0 4 = 1(3+1)+0 8 = 2(3+1)+0 12 = 3(3+1)+0 start new row
r=1 1 = 0(3+1)+1 5 = 1(3+1)+1 9 = 2(3+1)+1 13 = 3(3+1)+1 start new row
r=2 2 = 0(3+1)+2 6 = 1(3+1)+2 10 = 2(3+1)+2 end

Now we need consider how to insert a character between tow columns in the middle rows.

We can see, the r is larger, the insert character is more near by left. For example, "PAYPALISHIRING", numRows=4:

P     I    N
A   L S  I G
Y A   H R
P     I
c=0 c=1 c=2
r=0 0 6 12
r=1 1 5 7 11 13
r=2 2 4 8 10
r=3 3 9

Assume we insert a character to left, the current index is i. Then the inserted character is: \(i - 2r\)

class Solution {
public:
	string convert(string s, int numRows) {
		// The another corner case we should noticed
		if (numRows == 1) {
			return s;
		}
		int c = 0;
		int r = 0;
		int i = 0, j = 0;
		int d = numRows - 2;
		string res;
		while (true) {
			i = c * (numRows + d) + r;

			// neither head nor tail
			if (r > 0 && r < numRows - 1) {
				j = i - (2 * r);
				if (j > 0 && j < s.size()) {
					res.push_back(s[j]);
				}
			}
			if (i < s.size()) {
				res.push_back(s[i]);
				c++;
			} else {
				r++;
				if (r >= numRows) {
					break;
				}
				c = 0;
			}
		}
		return res;
	}
};