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
| class Solution {
public String convert(String s, int numRows) {
if (s == null || s.length() == 0 || numRows <= 1) {
return s;
}
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < rows.length; i++) {
rows[i] = new StringBuilder();
}
char[] sArray = s.toCharArray();
boolean down = true;
for (int i = 0, row = 0; i < sArray.length; i++) {
rows[row].append(sArray[i]);
if (down) {
if (row == rows.length - 1) {
row -= 1;
down = false;
} else {
row += 1;
}
} else {
if (row == 0) {
row += 1;
down = true;
} else {
row -= 1;
}
}
}
StringBuilder ans = new StringBuilder();
for (StringBuilder row : rows) {
ans.append(row);
}
return ans.toString();
}
}
|
和那个diagonal traversal matrix是一样的.
时间复杂度: O(n) n是s的长度. 因为就是遍历所有字符.
空间复杂度: O(n) 因为我们要存每个字符在对应的row中.
