6. ZigZag Conversion

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

这道题是一道比较容易的字符串操作题，只要找到其中的规律其实就没有什么难度了。

我们可以用一个vector<string>来保存我们的答案，这是因为，我们需要先将一个字符串转换为nRows个字符串。之后，我们每次用一个指针指向字符串起始位置，同时设置计数变量row来标记其在vector<string>中的位置即可。

下面对循环及逻辑判断的条件进行讨论，当我们的计数变量row小于nRows-1的值时，说明vector<string>没有构造完成，我们应该让字符串上的指针继续向前，同时计数变量row继续前进，也就是说进入下一行继续构造vector<string>

若两值相等，则说明我们该让计数变量row回退一下，即退回上一行继续构造vector<string>

厘清思路后，代码就很容易看明白了

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1||numRows>s.size()||numRows==s.size())
            return s;
        vector<string> str(numRows);
        int step=1,row=0;
        for(int i=0;i<s.size();++i){
            str[row].push_back(s[i]);
            if(row==0)
                step=1;
            else if(row==numRows-1)
                step=-1;
            row+=step;
        }
        s.clear();
        for(int j=0;j<str.size();++j)
            s.append(str[j]);
        return s;
    }
};

P.S 如果你对ZigZag Pattern的理解有疑惑的话，请记住这道题是这样定义ZigZag Pattern的。

/*n=numRows
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4
*/