LeetCode: ZigZag Conversion

Question

• https://leetcode.com/problems/zigzag-conversion
• Level: Medium
• Type: String, Implementation

Core Logic

Time Complexity: O(N)

• As you can see picture below[numRow=4]
  
• When 'zig-zag' appear[in picture, index 1, 4, 5]
  • We can find out that (eachIndex % (numRow-1)) is NOT zero.
  • Also, (eachIndex % (numRow-1)) also denotes 'Gap' from bottom.
    • For example, Let columnIndex = 2, and numRow=4[See Table above]
    • 2 % 3 = 2, the letter 'L' should be written 2 above from bottom
  • so, in Zig-Zag case, just put letter to table, with gap calculated.
• Continues, and finishes!

Algorithm

We are not making table itself, but we simulate each index, especially columnIndex

• Preprocess: Make empty string array, size of numRows
• Iterate through input string
  • when rowIndex %(numRows-1) == 0
    • It means we are on non-zig-zag area.
    • so, we append character on vector[numRows]
    • Update rowIndex / columnIndex
  • when rowIndex % (numRows-1) != 0
    • It means we are on zig-zag area.
    • So, we calculated gap, as I noted above core logic.
    • Append character on vector[gap]
• At the end, concat strings through string array and return it.

Code

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> eachRowText(numRows, "");
        int columnIndex = 0;
        int rowIndex = 0;
        int stringIndex = 0;

        while (stringIndex < s.length()) {
            if (columnIndex % (numRows-1) == 0) {
                // All Four
                while (rowIndex < numRows) {
                    if (stringIndex >= s.length()) {
                        break;
                    }
                    eachRowText[rowIndex++].push_back(s[stringIndex++]);
                }
                rowIndex = 0;
                columnIndex++;
            } else {
                int gap = columnIndex % (numRows-1); // Gap between Below
                eachRowText[numRows-1-gap].push_back(s[stringIndex]);
                columnIndex++;
                stringIndex++;
            }
        }
        
        string finalString = "";
        for (string tmpString : eachRowText) {
            finalString.append(tmpString);
        }

        return finalString;
    }
};

Submission