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:
P A H N
A P L S I I G
Y I R
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
PAYPALISHIRING
Solution
This kind of problem test if we can handle large amount of details in a reasonable time. We need to walk through a few special cases and form a formula. The formula can calculate the index or space between indexes, the variables are number of lines k, row number i and column number j.
Here is an example formula:
We divide the zigZag into many V shapes. We can increase j by 2k - 2 to get the next V shape on the right.
To calculate the space between the first index and second index on the V shape, we we can use formula j + 2k - 2 - 2i.
0 10 20 k = 6
1 9 11 19 21 2*(k-i) - 2 = 2 * (6-1) -2 = 8
2 8 12 18 22 2k - 2 - 4
3 7 13 17 23 - 6
4 6 14 16 24 - 8
5 15 25
0, 6, 12, |18 j + 2k - 2
1, 5,7 11 13, |19 j + 2k - 2 - 2i
2,4, 8 10 14, |20 j + 2k - 2 - 2i
3, 9 15, |21 j + 2k - 2
class ZigZag {
//PAYPALISHIRING -> PINALSIGYAHRPI
// .
//PINALSIGYA
//time O(N), space O(N)
public static String transform(String str, int k) {//4
if(k == 1) return str;
char[] a = str.toCharArray();
int N = a.length;//14
StringBuilder sb = new StringBuilder();
for(int i = 0; i < k; i ++) { //2
if(i == 0 || i == k - 1) {
for(int j = i; j <= N - 1; j+=(2*k - 2)) //6
sb.append(a[j]);
} else {
for(int j = i; j <= N - 1; j+=(2*k - 2)) {//2
sb.append(a[j]);
if(j + 2*k - 2 - 2*i < N - 1) {
sb.append(a[j + 2*k - 2 - 2*i]); //2 + 8 - 2 - 4 = 4
}
}
}
}
return sb.toString();
}
public static void main(String...args) {
String str = "PAYPALISHIRING";
System.out.println(transform(str, 3));
}
}
//PAYPALISHIRING -> PINALSIGYAHRPI
// .
//PINALSIGYA
//time O(N), space O(N)
public static String transform(String str, int k) {//4
if(k == 1) return str;
char[] a = str.toCharArray();
int N = a.length;//14
StringBuilder sb = new StringBuilder();
for(int i = 0; i < k; i ++) { //2
if(i == 0 || i == k - 1) {
for(int j = i; j <= N - 1; j+=(2*k - 2)) //6
sb.append(a[j]);
} else {
for(int j = i; j <= N - 1; j+=(2*k - 2)) {//2
sb.append(a[j]);
if(j + 2*k - 2 - 2*i < N - 1) {
sb.append(a[j + 2*k - 2 - 2*i]); //2 + 8 - 2 - 4 = 4
}
}
}
}
return sb.toString();
}
public static void main(String...args) {
String str = "PAYPALISHIRING";
System.out.println(transform(str, 3));
}
}
We visited each character once, the time complexity is O(N). A StringBuilder is used to store the converted string so the space complexity is O(N) as well.
