If you are confused with zigzag pattern,come and see!

• ``````/*n=numRows
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4
*/
``````

that's the zigzag pattern the question asked!
Be careful with nR=1 && nR=2

my 16ms code in c++:

``````class Solution {
public:
string convert(string s, int numRows) {
string result="";
if(numRows==1)
return s;
int step1,step2;
int len=s.size();
for(int i=0;i<numRows;++i){
step1=(numRows-i-1)*2;
step2=(i)*2;
int pos=i;
if(pos<len)
result+=s.at(pos);
while(1){
pos+=step1;
if(pos>=len)
break;
if(step1)
result+=s.at(pos);
pos+=step2;
if(pos>=len)
break;
if(step2)
result+=s.at(pos);
}
}
return result;
}
};``````

• Good explanation for those who don't know what zigzag string is, thanks!

• Thanks a lot for ZigZag explanation, I really don't get the idea from the problem. Thanks a lot!

• Thanks a lot. The question description was not clear at all and the example is kind of special, which does not help much.

• Also go check the graphs in this blog: https://segmentfault.com/a/1190000005751185, it helps a lot to think Zigzag as a Sinusoidal(i.e. sine wave).

• Thanks for your explanation. I have a more concise C++ solution

``````class Solution {
public:
string convert(string s, int numRows) {
if( numRows==1 ) return s;
vector<string> res(numRows);
int row=0;
int increase=-1;
for(int i=0; i<s.size(); ++i){
// every time at turning point, we change the increase direction
if(i%(numRows-1)==0) increase *= -1;
res[row].push_back(s[i]);
row += increase;
}
string ret;
for(const auto& str:res){
ret += str;
}
return ret;
}
};
``````

• @yanchao_hust Right and easy to understand, but slower. 36ms in total.

• My 9 ms Simple Java Solution

``````public String convert(String s, int numRows) {
//actually to find the pattern of indexes
//special conditions numRows:1
if (numRows == 1) return s;
int offset = 2 * numRows - 2;
StringBuffer result = new StringBuffer();
for (int i = 0; i < numRows; i ++) {
//first and last row increase a model
//zigzag pattern is an upside down N pattern
for (int j = 0; j*offset + i < s.length(); j ++) {
result.append(s.charAt(j*offset + i));
if (i != 0 && i != numRows - 1 && (j+1)*offset - i < s.length()) result.append(s.charAt((j+1)*offset - i));
}
}
return result.toString();
}
``````

• 5ms solution...

``````public String convert(String str, int R) {
if (R == 1) return str;

char[] s = str.toCharArray();
char[] t = new char[s.length];

for (int i = 0, len = 0; i < R; i++) {
for (int j = 0, k = i; k < s.length; j++) {
t[len++] = s[k];
k += ((i == 0 || j % 2 == 0) && i != R - 1 ? 2 * (R - i - 1) : 2 * i);
}
}

return new String(t);
}``````

• Same idea but more short & simple c++ solution

``````class Solution {
public:
string convert(string s, int numRows) {
string res="";
if(numRows==1) return s;
for(int i=0; i < numRows; i++){
for(int j=0, k=i; k < s.size(); j++){
res += s[k];
k += ((i==0 || (j%2==0)) && (i!= numRows-1) )? 2*(numRows-i-1) : 2*i;
}
}
return res;
}
};`````````

• Thanks for the explanation about the zigzag!

• @s961206
Very slick solution, could you please elaborate regarding the increment of k?

k += ((i==0 || (j%2==0)) && (i!= numRows-1) )? 2*(numRows-i-1) : 2*i;

• @HelloKenLee Straightforward work!

• @HelloKenLee I love you!

• Thank you kindly for the explanation, made the problem clear and simple!

• concise code with thought-provoking explanation!

• Share my Java solution with the same idea but maybe a little bit concise.

1. `interval` starts from `2 * numRows - 2` and decrease by 2. (As same as the `step1` in @HelloKenLee solution).
2. In the `while` loop, `i` is 0 means we are in the first row and `interval` is 0 means we reach the last row. In both cases, we just need to avoid appending repeated characters. Otherwise, we append 2 characters.
``````public String convert(String s, int numRows) {
if(numRows == 1)    return s;
StringBuilder b = new StringBuilder();
int interval = 2 * numRows - 2;
int n = s.length();
for(int i = 0; i < numRows; i++){
int j = i;
while(j < n){
if(interval != 0)
b.append(s.charAt(j));
j += interval;
if(i != 0 && j < n)
b.append(s.charAt(j));
j += 2 * i;
}
interval -= 2;
}
return b.toString();
}
``````

• Thanks a lot !

• Thanks for explaining the ZigZag. The questions fail to clearly define the zigzag pattern. So, I had to make a lot of assumptions and keep trying different patterns. Thanks for making it easy.

• thanks~ explantion help me to understand the problem

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