6. 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".

输入与输出

class Solution {
public:
    string convert(string s, int numRows) {
        
    }
};

样例

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".

题解与分析

本题可以建立一个二维数组模拟 ZigZag 过程。时间复杂度为 O(n)，但是需要额外空间存储二维数组。下面给出一个不需要额外空间的解法，通过位置关系直接计算新字符串每一个位置在原字符串对应的位置。

注意要单独处理只有一行的情况。

C++ 代码如下：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1)
            return s;
        string re;
        int index = 0;
        while (index < s.size()) {
            re.push_back(s[index]);
            index += 2 * numRows - 2;
        }
        int colnum;
        for (int i = 1; i < numRows - 1; ++i) {
            index = i;
            colnum = 0;
            while (index < s.size()) {
                re.push_back(s[index]);
                index = colnum % 2 == 0 ? index + 2 * numRows - 2 - 2 * i : index + 2 * i;
                ++colnum;
            }
        }
        index = numRows - 1;
        while (index < s.size()) {
            re.push_back(s[index]);
            index += 2 * numRows - 2;
        }
        return re;
    }
};

该解法的时间复杂度为 O(N)。