[C++]Straight and easy way. O(n) both time and space complexity

• Code First

``````class Solution {
public:
string convert(string s, int nRows) {
if (nRows <= 1) return s;
string str;
int pos = 0, len = s.length(), offset = 0;
for (int i = 0; i < nRows; i++){      //for each row, find the elements and add to string str
pos = i, offset = 2 * (nRows - 1 - i);
while (pos < len){                //which mean str = str + s[pos]
str += s.substr(pos, 1);
if (i != 0 && i != nRows - 1 && pos + offset < len)
//if it's not the first or last line, we need add one more,
str += s.substr(pos + offset, 1);  //that is str = str + s[pos+offset]
pos += 2 * nRows - 2;
}
}
return str;
}
};
``````

First, read my comment in code line by line, you will understand my solution.

Then, let me show you more detail.

There is no doubt that there exist a pattern for each line.

``````//this is a zigzag sample
F          F          F       //First line
*        * *        * *
M1    M2   M3     M4         //Middle inle
*    *     *    *
*  *       *  *
L          L                 //Last line
``````

The first and last line of zigzag, each character are separated by 2 * (nRows - 1 ) chars in string s.

Middle lines between 0 and nRows-1, characters showed in pairs, which mean we need add two characters into the string str once.

In middle line showed above, M1 and M2 both need added to string str, and the distance in string s between M1 and M2 is exactly the same as M3, M4. The distance is the var offset in my code.

offset = 2 * (nRows - 1 - i) life is so short, let's skip the proof

The time complexity is O(n) undoubtedly, space as well.(n=s.length(), nothing to do with the nRows)

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