# 06 Zigzag Conversion

## Description

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

## First Thought

This zigzag form actually does not need to be written out. The string can be divided into groups by one zigzag, whose length is `rownum*2 - 2`

. Then every line can be calculated out.

For the first line, they are the head of each zigzag.

For the rest but not last, there would be two characters: counted from the front and counted from the end.

For the last line, they are the middle one.

Which gives us the code

## Code

Several details were missed by me in the beginning:

- The tail, which does not form a full zigzag should be calculated specially
- When
`numRow == 1`

,`numRow * 2 - 2 == 0`

and it should be treated specially

```
class Solution {
public:
string convert(string s, int numRows) {
string ans, c;
int setnum = numRows * 2 - 2;
if (setnum == 0) {
return s;
}
int sets = s.size() / setnum;
for (int j = 0; j < s.length(); j += setnum) {
ans.append(c = s[j]);
}
for (int i = 1; i < numRows-1; ++i) {
int j;
for (j = 0; j < sets; ++j) {
ans.append(c = s[j * setnum + i]);
ans.append(c = s[j * setnum + setnum - i]);
}
if (j * setnum + i < s.size())
ans.append(c = s[j * setnum + i]);
if (j * setnum + setnum - i < s.size())
ans.append(c = s[j * setnum + setnum - i]);
}
for (int j = setnum / 2; j < s.length(); j += setnum) {
ans.append(c = s[j]);
}
return ans;
}
};
```

## Complexity

**Time Complexity**

Each character are just visited randomly once, so it is always $O(n)$.

**Space Complexity**

A new string is needed to store the output, so it is always $O(n)$.