6.ZigZag Conversion

Tags: Medium String

Links: https://leetcode.com/problems/zigzag-conversion/

---

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

---

class Solution {
public:
    string convert(string s, int numRows) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (numRows == 1) return s;

        vector<string> store(numRows);
        int preLine = 0;
        int direction = 0; //0代表向下,1代表向上

        int pos = 1, n = s.size();
        while (pos <= n) {
            store[preLine].push_back(s[pos - 1]);

            if ((pos + numRows - 2) % (numRows - 1) == 0) { //需要反转方向了
                if (preLine == 0) direction = 0;
                else if (preLine == numRows - 1) direction = 1;
            } 

            ++pos;
            if (direction) --preLine;
            else ++preLine;
        }
        string res;
        for (auto e : store) res += e;

        return res;
    }
};