# 16ms and O(n) c++ soution. Fastest in C++

• Given an index i of `string s`, if we can calculate the index of the new string, then it's an O(n) solution. Here is how I do it. Let's see the code first.

``````class Solution {
public:
string convert(string s, int numRows) {
if(numRows <= 1)
return s;
int period = numRows * 2 - 2;// this constant is very important.
string ret;
for(int i = 0; i < numRows; i++)//iterate by row number
{
int n = 0;
for(int j = i; j < s.size();)
{
ret += s[j];
/* the following 4 lines gives the next j should be */
if(i == 0 || i == numRows - 1)
j += period;
else
j = (++n) * period - j;
}
}
return ret;
}
};
``````

what really confuses me at first is the relation between row number and the letters should be in the row. I draw a graph, simply explain it. Take the `PAYPALISHIRING` for example, and `row = 4`;
if you can't see the picture, link is here 链接在这里 or here

Now, it's brief. if row is 0 or numRows - 1, `n*6+row` the next position; if it's not, `n*6-row` is the next position, where n is an counter, from 1 to value which it can grow but won't make j >= s.size()

• I can't see pictures, what can i do?

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