# 22ms one-pass O(n)-time C++ solution with explanation

• numRows=3
|P. |...|....|....| A |....|....|....| H |... |...|....| N |...|
|....|A |....| P |....| L |....| S |....| I .|...| I .|....|G |
|....|...|.Y |....|....|....|. I |....|... | ...|R |....|....|....|
| 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10|11|12|13| Column
| 0 |1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | num = Column % (2 * numRows - 2)
| 0 |1 | 2 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | num < numRows ? num : (2 * numRows - 2) - num

the problem as the same as
|0|1|2|3|
|0|1|2|1|

class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1)
return s;
string *ss = new string[numRows], rs;
for (int i = 0; i < s.size(); i++){
int num = i % (2 * numRows - 2);
ss[num < numRows ? num : (2 * numRows - 2) - num].push_back(s[i]);
}
for (int i = 0; i < numRows; i++){
rs += ss[i];
}
delete[] ss;
return rs;
}

/*
numRows=3
|P| | | |A| | | |H| | | |N | |
| |A| |P| |L| |S| |I| |I | |G |
| | |Y| | | |I| | | |R | | | |
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|
|0|1|2|3|0|1|2|3|0|1|2 |3 |0 |1 | Column % (2 * numRows - 2)
|0|1|2|1|0|1|2|1|0|1|2 |1 |0 |1 |

numRows=4
|P| | | | | |I| | | | | |N | |
| |A| | | |L| |S| | | |I | |G |
| | |Y| |A| | | |H| |R | | | |
| | | |P| | | | | |I| | | | |
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|
|0|1|2|3|4|5|0|1|2|3|4 |5 |0 |1 | Column % (2 * numRows - 2)
|0|1|2|3|2|1|0|1|2|3|2 |1 |0 |1 |
the problem as the same as
|0|1|2|3|
|0|1|2|1|

|0|1|2|3|4|5|
|0|1|2|3|2|1|

*/
}；

0_1487322469373_6_ZigZag Conversion .cpp

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