Monday, November 25, 2013

LeetCode Problem : ZigZag Conversion

Problem

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

Code

string convert(string s, int nRows) {
    // Note: The Solution object is instantiated only once and is reused by each test case.    
    int n = s.size();
    if(nRows == 1)
        return s;
    bool bleft;
    int lgap = 2*(nRows - 1);
    int rgap = 0;
    int count = 0,offset;
    string out;
    out.resize(n);
    for(int i = 0;i < nRows; ++i){
        offset = i; 
        bleft = false;
        while(offset < n){
            out[count++] = s[offset];
            bleft = !bleft;
            if(i == 0)
             offset += lgap;
            else if(i == nRows - 1)
             offset += rgap;
            else
             offset += (bleft ? lgap : rgap);
        }
        lgap -= 2;
        rgap += 2;
    }
    return out;
}

No comments:

Post a Comment