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

1. The tail, which does not form a full zigzag should be calculated specially
2. 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)$.

##### penway Wang
###### Mechanic Technical Director

My research interests include computer vision, artificial intelligence and software engineering. I am a FSAE race car crew member at the same time, designing suspension system.

Previous