Saturday, September 14, 2013

ZigZag Conversion

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

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function   
        if (nRows <= 1) return s;
        int size = s.size();
        if(size <= nRows) return s;
        int step = 2*nRows-2;
        int round = size/step + 1;
        int i, k, index;
        string result;
        for(i=0; i<nRows; i++){
           for(k=0; k<round; k++){
              index = i + k*step;
              if(index<size){
                result.push_back(s[index]);
              }
             
              if(!(i==0 || i== (nRows-1))){
                index = index + step - 2*i;
                if(index<size){
                 result.push_back(s[index]);
                }
              } //end if
           } //end inner for
        } //end outer for
       
        return result;
    }
    };

No comments:

Post a Comment