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

Subscribe to see which companies asked this question.

 1 class Solution {
 2 public:
 3     string convert(string s, int numRows) {
 4         if(numRows==1) return s;
 5         int length=s.length();
 6         char table[numRows][length*length/numRows*2+1];
 7         for(int r=0;r<numRows;r++)
 8         {
 9             for(int c=0;c<length*length/numRows*2+1;c++)
10             {
11                 table[r][c]=' ';
12             }
13         }
14         bool tag=0;
15         int r=-1,c=0,i=0;
16         while(1)
17         {
18             if((r==0||tag==0)&&r<numRows-1)
19             {
20                 tag=0;
21                 r++;
22                 //cout<<"r="<<r<<",c="<<c<<",code="<<s[i];
23                 table[r][c]=s[i];
24                 i++;
25                 //cout<<",i="<<i<<endl;
26             }
27             if(i>=s.length()) break;
28             if((r==numRows-1||tag==1)&&r>0)
29             {
30                 tag=1;
31                 c++;
32                 r--;
33                 //cout<<"r="<<r<<",c="<<c<<",code="<<s[i];
34                 table[r][c]=s[i];
35                 i++;
36                 //cout<<",i="<<i<<endl;
37             }
38             if(i>=s.length()) break;
39         }
40         string ans;
41         for(int r=0;r<numRows;r++)
42         {
43             for(int c=0;c<length*length/numRows*2+1;c++)
44             {
45                 if(table[r][c]!=' ')
46                 {
47                     ans+=table[r][c];
48                 }
49             }
50         }
51         return ans;
52     }
53 };