Zigzag Conversion

Zigzag Conversion

This problem is from leetcode.com.

Problem Description:

---

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)

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

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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Analysis:

---

Let's first take text = "abcdefghijklmnopqrstuvwxyz" and nRows = 4 as another example. The Zigzag pattern should like this:

a  g  m  s  y
b fh ln rt xz
ce ik oq uw
d  j  p  v

If we ingore the blank spaces between letters in each line, the Zigzag pattern is generated by placing text letters in each line sequentially. First the heading direction is up-bottom, we place 'a', 'b', 'c' and 'd' from the 1st line to the 4th line. And when we reach the bottom line the heading direction should be reversed. Then 'e', 'f' and 'g' are placed from the 3rd line to the 1st line. Each time we reach the top or bottom line the heading direction is reversed.

As the final result is generated by reading letters line by line and space is omited, space is not needed to be considered while generating the Zigzag pattern. Therefore, the pattern actually is of the following form:

agmsy
bfhlnrtxz
ceikoquw
djpv

We can use a vector to store letters in each line. After placing all letters, reading letters in each vector one by one gives us the final result.

Code (C++):

---

string convert(string s, int nRows) {
    int len = s.length();
    if (len < 3 || nRows == 1)
        return s;

    bool down = true;
    vector<vector<int> > tab(nRows);
    for (int i = 0, row = 0; i < len;) {
        if (down && row < nRows) 
            tab[row++].push_back(s[i++]);
        else if (!down && row >= 0)
            tab[row--].push_back(s[i++]);

        if (row < 0 || row >= nRows) {
            row += (down ? -2 : 2);
            down = !down;
        }
    }

    string ret = "";
    vector<vector<int> >::iterator it = tab.begin();
    for (; it != tab.end(); ++it) {
        vector<int>::iterator it2 = (*it).begin();
        for (; it2 != (*it).end(); ++it2)
            ret += *it2;
    }
    return ret;
}

-End-