6. ZigZag Conversion

• Difficulty: Medium

• Topics: String

• Similar Questions:

Problem:

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 s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

Solutions:

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 0)    return "";
        if (numRows == 1)   return s;
        int period = 2 * (numRows - 1);
        string ret;
        for (int row = 0; row < numRows; ++row) {
            for (int i = row; i < s.length(); i = i + period) {
                ret.push_back(s[i]);
                if (row != 0 && row != numRows - 1 && i + (numRows - 1 - row) * 2 < s.length()) {
                    ret.push_back(s[i + (numRows - 1 - row) * 2]);
                }
            }
        }

        return ret;
    }
};

More intuitive solution

Use multiple strings.

From [https://www.cnblogs.com/grandyang/p/4128268.html]Grandyang:

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) return s;
        string res;
        int i = 0, n = s.size();
        vector<string> vec(numRows);
        while (i < n) {
            for (int pos = 0; pos < numRows && i < n; ++pos) {
                vec[pos] += s[i++];
            }
            for (int pos = numRows - 2; pos >= 1 && i < n; --pos) {
                vec[pos] += s[i++];
            }
        }
        for (auto &a : vec) res += a;
        return res;
    }
};