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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

tag: string

9/24/2015 update

Another approach, view the zigzag graph as separated groups.

0-5 belongs to group 1, 6-11 belongs to group 2, etc…

0    6      12
1  5 7   11 13
2 4  8 10   14
3    9      15
*--* *----* *---
(1)    (2)    (3)---

assume there are n rows, gap between the same location element in adjacent groups is 2 * (n – 1)

class Solution {
public:
    string convert(string s, int numRows) {
        string ans;
        if(numRows == 0) return "";
        if(numRows == 1) return s;
        int gap = 2 * (numRows - 1);
        for(int i = 0; i < numRows; i++){
            if(i == 0){
                //first line
                int j = 0;
                while(j < s.size()){
                   ans.push_back(s[j]);
                   j += gap;
                }
            }
            else if(i == numRows - 1){
                //last line
                int j = i;
                while(j < s.size()){
                    ans.push_back(s[j]);
                    j += gap;
                }
            }
            else{
                //in the middle lines
                int j1 = i;
                int j2 = 2 * (numRows - 1) - j1;
                while(j2 < s.size()){
                    ans.push_back(s[j1]);
                    ans.push_back(s[j2]);
                    j1 += gap;
                    j2 += gap;
                }
                if(j1 < s.size()){
                    ans.push_back(s[j1]);
                }
            }
        }
        return ans;
    }
};

觉得是个数学题。我的思路是按zigzag图形的每行进行扫描，找规律计算出每个点对应的string的索引值，将该字符压入re中。

网上的关于zigzag的解释不多，大都是讲另一个zigzag螺旋矩阵。本题指的是并列排列的N字形矩阵。

他有点像： | / | / | / | / |

我们取每个N的左边一竖和中间的斜线作为循环单位“| /”，利用offset进行单位间的偏移。

需要注意的是，我们要把nRow=1的情况单独考虑，否则会导致offset为0，死循环，而内存超界。

class Solution {
public:
    string convert(string s, int nRows) {
        string re;
        if(nRows == 1){
            return s;
        }
        for(int i = 0; i < nRows; i++){//for each row
            int offset = 0;//for each unit
            while(true){
                int index = offset + i;
                if(index >= s.size()){
                    break;
                }
                re.push_back(s[index]);
                if(i == 0 || i == nRows - 1){
                    offset += (nRows - 1) * 2;
                    continue;
                }
                index = offset + i + (nRows - i - 1) * 2;
                if(index >= s.size()){
                    break;
                }
                re.push_back(s[index]);
                offset += (nRows - 1) * 2;
            }
        }
        return re;
    }
};