Description
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:
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
AC代碼
class Solution {
public:
string convert(string s, int numRows) {
if(numRows <= 1) {
return s;
}
vector<string> pattern(numRows, "");
string res = "";
// down is a flag which determine the direction
int down = 0;
// row stands for which row it is now
int row = 0;
for(int i=0; i<s.size(); i++) {
pattern[row].push_back(s[i]);
if(row == 0) {
down = 1; // Move downside
} else if(row == numRows - 1) {
down = -1; // Move upside
}
row += down;
}
for(int i=0; i<numRows; i++) {
res += pattern[i];
}
return res;
}
};
測試代碼
int main() {
Solution s;
string s1 = "PAYPALISHIRING";
string res_s1 = s.convert(s1, 3);
cout << res_s1 << endl;
string s2 = "PAYPALISHIRING";
string res_s2 = s.convert(s2, 4);
cout << res_s2 << endl;
}
總結
使用犧牲空間復雜度的方式換取時間復雜度磷蜀，創(chuàng)建一個vector藕届，來存儲每一行的字符串贮竟。設置一個flag，決定index移動的方向左权。
