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 s, int numRows);
Example 1:
<preclass=”crayon:false”>Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR”
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Solution: Simulation
Store the zigzag results for each row and then output row by row.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua class Solution { public: string convert(string s, int nRows) { if (nRows == 1) return s; vector<string> ss(nRows); int l = s.length(); int x = 0, y = 0, i = 0; bool down = true; while (i < l) { ss[y] += s[i]; if (down) { ++y; if (y == nRows) { down = false; y -=2; } } else { --y; if (y < 0) { down = true; y = 1; } } i++; } string ans; for(const string& r : ss) ans += r; return ans; } }; |