LeetCode 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 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
基本想法就是先填充一个二维矩阵，再遍历矩阵拼接字符。
class Solution {
public String convert(String s, int numRows) {
int len = s.length();
if (len <= 1 || numRows == 1){
return s;
}
int period = 2*numRows-2;
char[][] mat = new char[numRows][(len/period+1)*(numRows-1)];
for(int i = 0; i < len; ++i){
if(i%period < numRows){
mat[i%period][(i/period)*(numRows-1)] = s.charAt(i);
}else{
mat[period-i%period][(i/period)*(numRows-1)+i%period-numRows+1] = s.charAt(i);
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < numRows; ++i){
for (int j = 0; j < (len/period+1)*(numRows-1); ++j){
if(mat[i][j] != 0){
sb.append(mat[i][j]);
}
}
}
return sb.toString();
}
}