题目描述
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)。
