Solving the 'Zigzag Conversion' on LeetCode with C++
Tags: leetcode
Published: 2023-07-11 10:39:49

## Problem
https://leetcode.com/problems/zigzag-conversion/

## Answer
```
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};
```

Let's consider the solution this problem.

```
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PAHNAPLSIIGYIR"

P   A   H   N
A P L S I I G
Y   I   R
```

We ask for the answer to combine the strings of each row from the first to the last row.

The first row is "PAHN".
The second row is "APLSIIG".
The third row is "YIR".

"PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR"

Let's write the above algorithm as code.
I repost the answer code.
```
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};
```

Let's break down the above code.
```
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }
```
We should return `s` if `numRows` is 1 because it's one row.

```
        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;
```
We need to take the minimum of `numRows` or the size of input `s`. Because if `numRows` is 4 and `s` has a size of 3, not all rows will be used.

`goingDown` indicates the moving direction, whether up or down in rows.

```
        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }
```
`rows[currentRow] += c;` creates a string for each row.

```
if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
```
It reverses `goingDown` if `currentRow` is the first row or `currentRow` is the last row.
It moves `currentRow` to the next row if `goingDown` is `true`.
It moves `currentRow` to the previous row if `goingDown` is false`

For example:
The number of rows is 3.

The start `currentRow` is 0. `goingDown` is `true` because rows move from top to bottom.
The next `currentRow` is 1. `goingDown` is `true` and the row still moves from top to bottom because the `currentRow` is not yet the last row.
The next `currentRow` is 2. `goingDown` changes from `true` to `false` because the `currentRow` is the last row. The next `currentRow` needs to be 1.

```
        string result;
        for(string row : rows) {
            result += row;
        }
```
It combines the strings of each row.