Algorithm Puzzles everyday every week sometimes: ZigZag Conversion

## Puzzle

Puzzle from leetcode:

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)

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 s, int numRows);
Example 1:

Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”
Example 2:

Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:

## Solution

### First came out solution

0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15

It’s obvious that the output is periodic for first row:

Let T = 2 * (numRows - 1), for next row(row[1]):

For row[2]:

Change 1,2 to rowIndex which start from 0 to numRows - 1 :

Cool, can start coding now

Result:

Let’s do some optimization:

Result:

Looks like we also can change size_t T = 2 * (numRows - 1) to size_t T = numRows + numRows -2 to use add instead of multiply

Result:

Super, better than 99.34% now!