sourcecode

Monday, December 10, 2012

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

For an input string "aaaaaaaaaaaaaa", you are getting an output | / | / | like pattern:
a___a___a
a__aa__aa
a_a_a_a_a
aa__aa__a
a___a___a
class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function  
        string r(s);
        if (nRows <= 1) return r;
        int rii = 0;
        for(int nn = 0; nn < s.size(); nn += (nRows-1)*2){//first row
            r[rii++] = s[nn];
        }
        for(int row = 1; row+1 < nRows; ++row){
            for(int nn = row; nn < s.size(); nn += (nRows-1)*2){
                r[rii++] = s[nn];
                int secondIndex = nn + (nRows-row-1)*2;
                if (secondIndex < s.size()) r[rii++] = s[secondIndex];
            }
        }
        for(int nn = nRows-1; nn < s.size(); nn += (nRows-1)*2){//last row
            r[rii++] = s[nn];
        }
        
        return r;
    }
};

No comments: