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)$