<p>The string <code>&quot;PAYPALISHIRING&quot;</code> 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)</p>

<pre>
P   A   H   N
A P L S I I G
Y   I   R
</pre>

<p>And then read line by line: <code>&quot;PAHNAPLSIIGYIR&quot;</code></p>

<p>Write the code that will take a string and make this conversion given a number of rows:</p>

<pre>
string convert(string s, int numRows);
</pre>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;PAYPALISHIRING&quot;, numRows = 3
<strong>Output:</strong> &quot;PAHNAPLSIIGYIR&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;PAYPALISHIRING&quot;, numRows = 4
<strong>Output:</strong> &quot;PINALSIGYAHRPI&quot;
<strong>Explanation:</strong>
P     I    N
A   L S  I G
Y A   H R
P     I
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;A&quot;, numRows = 1
<strong>Output:</strong> &quot;A&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists of English letters (lower-case and upper-case), <code>&#39;,&#39;</code> and <code>&#39;.&#39;</code>.</li>
	<li><code>1 &lt;= numRows &lt;= 1000</code></li>
</ul>

#define DEBUG 0
class Solution {
public:
    vector<vector<char>> createZigZagVector(int numRows)
    {
        vector<vector<char>> zigZagVector;
        vector<char> emptyCharVector;

        for (unsigned int i = 0; i < numRows; i++)
        {
            zigZagVector.push_back(emptyCharVector);
        }

        return zigZagVector;
    }

    void printZigZagVector(vector<vector<char>> zigZag)
    {
        for (unsigned int i = 0; i < zigZag.size(); i++)
        {
            cout << "row " << i << ": ";
            for (unsigned int j = 0; j < zigZag.at(i).size(); j++)
            {
                cout << zigZag.at(i).at(j) << " ";
            }

            cout << endl;
        }
    }

    string convertVectorToStr(vector<vector<char>> zigZag)
    {
        string convertedStr = "";
        for (unsigned int curRowIndex = 0; curRowIndex < zigZag.size(); curRowIndex++)
        {
            for (unsigned int curCharIndex = 0; curCharIndex < zigZag.at(curRowIndex).size(); curCharIndex++)
            {
                convertedStr += zigZag.at(curRowIndex).at(curCharIndex);
            }
        }

        return convertedStr;
    }

    string convert(string s, int numRows) 
    {
        if (numRows == 1)
            return s;

        vector<vector<char>> zigZag = createZigZagVector(numRows);
        int curRow = 0;
        bool diagonalTime = false;

        for (unsigned int i = 0; i < s.size(); i++)
        {
            if (DEBUG) {cout << "pushing " << s.at(i) << " to row " << curRow << endl;}
            zigZag.at(curRow).push_back(s.at(i));

            if (!diagonalTime)
                curRow++;

            if (curRow >= numRows) {
                diagonalTime = true;
                curRow--;
            }

            if (diagonalTime)
            {
                if (curRow > 0) {
                    curRow--;
                }
                else {
                    diagonalTime = false;
                    curRow = 1;
                }
                    
            }
        }

        if (DEBUG) {printZigZagVector(zigZag);}

        return convertVectorToStr(zigZag);
    }
};
24143