6 ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows.
Solution:
class Solution {
public:
string convert(string s, int numRows) {
/*
T = numRows*2-2
0 6 T*i
1 5 7 d1 = T-2, d2 = 2
2 4 8 d1 = T-4, d2 = 4
3 9 numRows-1 + T*i
*/
if ( numRows == 1 ) return s;
int T = numRows*2-2, n = s.size();
string res = "";
for ( int i = 0; i <= numRows-1; i++ ) {
int d1 = T-2*i;
if ( i == 0 ) {
for ( int j = 0; j*d1 <= n-1; j++ ) res += s[j*T];
continue;
}
if ( d1 == 0 ) {
for ( int j = 0; numRows-1+j*T <= n-1; j++ ) res += s[numRows-1+j*T];
continue;
}
int j = 0;
while (true) {
if ( i + j*T>= n ) break;
res += s[i + j*T];
if ( i + j*T + d1 >= n ) break;
res += s[i + j*T + d1];
j += 1;
}
}
return res;
}
};