Solution by RoyLeo

• firstly, we find the law;

for example,we have a string of length 10,and numRows = 4.

all we need to do is find the map {0,1,2,3,4,5,6,7,8,9} -> {0,1,2,3,2,1,0,1,2,3}
the result string is periodic ,say,{0,1,2,3,2,1} ,the period is 6,and the law is :[ (numRows-1)*2 ]

1. construct the base sequence: {0,1,...,numRows-1,numRows-2,...1}
for vector "base" of length 2*(numRows-1) i:0- 2*(numRows-1)-1
if i <= numRows-1 base[i] = i;
else base[i] = 2*(numRows-1) -i; //symmetry

2. In terms of periodicity,
the char's index of string belong to which line is
index = s[i % Size],where Size = 2*(numRows-1)
this is the keypoint
so we can use numRows string to store intermediate result

3. merge every sring, we get result

the cpp solution is as follows:
''''
class Solution {
public:
string convert(string s, int numRows) {

``````	int len = s.length();

if(numRows <= 0) return NULL;
if(len <= numRows) return s;
if(numRows == 1) return s;

//get base sequeue eg {0,1,2,3,2,1}
vector<int> base;
int Size = (numRows-1)*2;
assert( Size != 0);
for(int i = 0; i < Size ;++i)
{
if(i <= numRows-1) base.push_back(i);
else base.push_back(2*(numRows-1)-i);
}

vector<vector<char>> res(numRows);
for(int i  = 0; i < len ;++i)
{
int index = base.at(i % (Size));
res[index].push_back(s.at(i));
}

//merge result
string dst;
for(int i = 0; i < numRows;++i)
{
int cnt = res[i].size();
for(int j = 0; j < cnt; ++j)
{
dst += res[i][j];
}
}
return dst;
}
``````

};
'''''''

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