Reference: LeetCode
Difficulty: Medium

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)

1
2
3
P   A   H   N
A P L S I I G
Y I R

And then read line by line: "PAHNAPLSIIGYIR"

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P I N
A L S I G
Y A H R
P I

Analysis

ZigZag Simulation

Use extra numRows buckets to simulate the ZigZag process.

Note:

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
35
36
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
int n = s.length();
// buckets
List<StringBuilder> sbList = new ArrayList<>();
for (int i = 0; i < numRows; ++i) {
sbList.add(new StringBuilder());
}
// simulation
int row = 0, idx = 0;
boolean goingDown = true;
while (idx < n) {
sbList.get(row).append(s.charAt(idx));
// update
if (goingDown) row += 1;
else row -= 1;
// out-of-bound
if (row > numRows - 1) {
goingDown = false;
row = (numRows - 1) - 1;
}
if (row < 0) {
goingDown = true;
row = 1;
}
count += 1;
}
// concatenate
StringBuilder result = new StringBuilder();
for (StringBuilder sb : sbList) {
result.append(sb);
}
return result.toString();
}

Time: $O(N)$
Space: $O(N)$

Visit by Row

By observation, consider the following cases:

  • Characters in row 0.
  • Characters in row numRows - 1.
  • Characters in inner rows.

Just analyze the examples below and find the rules for indexing. The index for inner rows is tricky and a bit complex. Try to think how to make the current row number contribute.

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
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
0 1 2 3 4 5 6 7 8 9 10 11 12 13
P A Y P A L I S H I R I N G

row = 3, offset = 2 * 3 - 2 = 4
0 4 8 12
P A H N // i = 0
1 3 5 7 9 11 13
A P L S I I G // i = 1
2 6 10
Y I R // i = 2

row = 4, offset = 2 * 4 - 2 = 6
0 6 12
P I N // i = 0
1 5 7 11 13
A L S I G // i = 1
2 4 8 10
Y A H R // i = 2
3 9
P I // i = 3

Note: Be careful of the corner case numRows == 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
int n = s.length();
StringBuilder sb = new StringBuilder();
int offset = 2 * numRows - 2;
for (int i = 0; i < numRows; ++i) {
for (int j = 0; i + j < n; j += offset) {
int idx = i + j; // i + offset, i + offset * 2, i + offset * 3
sb.append(s.charAt(idx));
int innerIdx = idx + offset - 2 * i;
if (i != 0 && i != numRows - 1 && innerIdx < n) { // consider inner row
sb.append(s.charAt(innerIdx));
}
}
}
return sb.toString();
}

Time: $O(N)$
Space: $O(1)$


Comment