解説
文字列を1文字ずつ走査し、現在の行のビルダーに文字を追加します。行インデックスは 下または上へ1つずつ進み、最初または最後の行に到達したら進行方向を反転します。 すべての文字を配置した後、行ビルダーを上から順に連結すると変換後の文字列になります。 行が1つだけの場合、または行数が文字数以上の場合は斜めの移動がないため、入力を そのまま返します。
この方法ではジグザグの走査を直接シミュレーションします。各文字を走査中に占める行へ 配置し、行順に読み出すため、求める結果と一致します。N 文字をそれぞれ一度ずつ 追加して読み出すので、時間計算量は O(N) です。行ビルダーと結果に O(N) の 空間を使用します。
Java
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
import java.util.ArrayList;
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) {
return s;
}
ArrayList<StringBuilder> rows = new ArrayList<>(numRows);
for (int row = 0; row < numRows; row++) {
rows.add(new StringBuilder());
}
int currentRow = 0;
int direction = 1;
for (int i = 0; i < s.length(); i++) {
rows.get(currentRow).append(s.charAt(i));
if (currentRow == 0) {
direction = 1;
} else if (currentRow == numRows - 1) {
direction = -1;
}
currentRow += direction;
}
StringBuilder result = new StringBuilder(s.length());
for (StringBuilder row : rows) {
result.append(row);
}
return result.toString();
}
}