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:
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
We create an 2-D array, fill it with the characters, then read line by line to get the answer.
We can re-arraynge the fills, each column has numOfRow -1 characters, go down column start at 0, go up column start at last row.
/*
P I N
A L S I G
Y A H R
P I
*/
class Solution {
public String convert(String s, int numRows) {
if(s == null || s.length() == 0) return "";
if(numRows == 1) {
return s;
}
char[][] arr = new char[numRows][s.length()/(numRows-1)+1];
boolean down = true;
int counter = 1;
int row = 0;
int col = 0;
for(char c : s.toCharArray()) {
arr[row][col] = c;
row += down ? 1 : -1;
if(counter == numRows - 1) {
if(down) {
row = arr.length - 1;
} else {
row = 0;
}
down = !down;
counter = 1;
col++;
} else {
counter++;
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr[0].length; j++) {
if(arr[i][j] != '\u0000') {
sb.append(arr[i][j]);
}
}
}
return sb.toString();
}
}
Time complexity: O(N), each character need to be processed once.
Space complexity: O(N), the 2-D matrix has roughly numOfRows x (N/numOfRows) with is proportional to N.
