# [leetcode] ZigZag Conversion

### ZigZag Conversion

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

```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:

`string convert(string text, int nRows);`

`convert("PAYPALISHIRING", 3)` should return `"PAHNAPLSIIGYIR"`.

tag: string

9/24/2015 update

Another approach, view the zigzag graph as separated groups.

0-5 belongs to group 1, 6-11 belongs to group 2, etc…

```0    6      12
1  5 7   11 13
2 4  8 10   14
3    9      15
*--* *----* *---
(1)    (2)    (3)---```

assume there are n rows, gap between the same location element in adjacent groups is 2 * (n – 1)

```class Solution {
public:
string convert(string s, int numRows) {
string ans;
if(numRows == 0) return "";
if(numRows == 1) return s;
int gap = 2 * (numRows - 1);
for(int i = 0; i < numRows; i++){
if(i == 0){
//first line
int j = 0;
while(j < s.size()){
ans.push_back(s[j]);
j += gap;
}
}
else if(i == numRows - 1){
//last line
int j = i;
while(j < s.size()){
ans.push_back(s[j]);
j += gap;
}
}
else{
//in the middle lines
int j1 = i;
int j2 = 2 * (numRows - 1) - j1;
while(j2 < s.size()){
ans.push_back(s[j1]);
ans.push_back(s[j2]);
j1 += gap;
j2 += gap;
}
if(j1 < s.size()){
ans.push_back(s[j1]);
}
}
}
return ans;
}
};```

```class Solution {
public:
string convert(string s, int nRows) {
string re;
if(nRows == 1){
return s;
}
for(int i = 0; i < nRows; i++){//for each row
int offset = 0;//for each unit
while(true){
int index = offset + i;
if(index >= s.size()){
break;
}
re.push_back(s[index]);
if(i == 0 || i == nRows - 1){
offset += (nRows - 1) * 2;
continue;
}
index = offset + i + (nRows - i - 1) * 2;
if(index >= s.size()){
break;
}
re.push_back(s[index]);
offset += (nRows - 1) * 2;
}
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.