2013.12.1 21:48

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   NA P L S I I GY   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:

1 string convert(string text, int nRows);

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

Solution:

　　This kind of problem is not complicated, and can be done with some calculation on the scratch before you start coding. Still, special cases need special handlings:

　　　　1. the string is empty

　　　　2. nRows = 1

　　Time complexity is O(n), where n is the length of the string. Space complexity is O(n) with the use of char array during the algorithm.

Accepted code:

1 //1RE, 1AC, special case needs special handling 2 class Solution { 3 public: 4     string convert(string s, int nRows) { 5         // IMPORTANT: Please reset any member data you declared, as 6         // the same Solution instance will be reused for each test case.     7          8         // 1RE here, ignored the special case where nRows == 1 9         if(nRows == 1){10             return s;11         }12         char *str = nullptr;13         int i, j, k, len;14         15         len = s.length();16         str = new char[s.length() + 1];17         j = 0;18         for(k = 0; k < nRows; ++k){19             if(k == 0){20                 for(i = 0; i < len; ++i){21                     if(i % (2 * nRows - 2) == 0){22                         str[j++] = s[i];23                     }24                 }25             }else if(k == nRows - 1){26                 for(i = 0; i < len; ++i){27                     if(i % (2 * nRows - 2) == nRows - 1){28                         str[j++] = s[i];29                     }30                 }31             }else{32                 for(i = 0; i < len; ++i){33                     if(i % (2 * nRows - 2) == k || i % (2 * nRows - 2) == 2 * nRows - 2 - k){34                         str[j++] = s[i];35                     }36                 }37             }38         }39         str[j] = 0;40         41         string res = string(str);42         delete[] str;43         return res;44     }45 };