Online Judge Solutions

Saturday, November 8, 2014

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) {
        if (nRows < 2) return s;
        int n = s.length();
        int groupLen = 2*nRows-2;
        int groups = 1 + n / groupLen;
         
        string output;
        for(int i = 0; i < nRows; i++)
        {
            for(int j = 0; j < groups; j++ )
            {
                if (i == 0 || i == nRows-1)
                {
                    if (j * groupLen + i <n)
                       output.push_back(s[j * groupLen + i]);
                }
                else {
                    if (j * groupLen + i <n)
                       output.push_back(s[j * groupLen + i]);
                    if ((j+1) * groupLen - i <n)
                       output.push_back(s[(j+1) * groupLen - i]);
                }
            }
        }
        return output;
    }
};

class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows < 2) return s;
       
        vector<string> map(nRows, "");
        int groupLen = 2*nRows-2;
       
        for(int i = 0; i < s.length(); i++)
        {
            int index = i % groupLen;
            if (index <nRows)
               map[index].push_back(s[i]);
            else
               map[groupLen-index].push_back(s[i]);
        }
       
        string output = "";
        for(string str:map)
           output += str;
        return output;
    }
};

No comments:

Post a Comment