DEV Community

Shiki Endou
Shiki Endou

Posted on

Solving the 'Zigzag Conversion' on LeetCode with C++

#leetcode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Let's break down the above code.

    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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;
        }
Enter fullscreen mode Exit fullscreen mode

rows[currentRow] += c; creates a string for each row.

if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)