/
Solution.java
79 lines (71 loc) · 2.14 KB
/
Solution.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
* Time : O(N) ; Space: O(N)
* @tag : String
* @by : Steven Cooks
* @date: Jul 20, 2015
***************************************************************************
* Description:
*
* 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 text, int nRows);
* convert("PAYPALISHIRING", 3)
* should return "PAHNAPLSIIGYIR".
*
***************************************************************************
* {@link https://leetcode.com/problems/zigzag-conversion/ }
*/
package _006_ZigZagConversion;
import java.util.ArrayList;
import java.util.List;
/** see test {@link _006_ZigZagConversion.SolutionTest } */
public class Solution {
private int[] indices;
public String convert(String s, int numRows) {
if (numRows <= 0) {
return "";
} else if (numRows == 1) {
return s;
}
// construct indices
constructIndices(numRows);
// zigzag converting
int index = 0;
List<StringBuilder> strs = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
strs.add(new StringBuilder());
}
for (int i = 0; i < s.length(); i++) {
if (index == indices.length) {
index = 0;
}
int j = indices[index];
strs.get(j).append(s.charAt(i));
index++;
}
// construct result
StringBuilder str = new StringBuilder();
for (StringBuilder ss : strs) {
str.append(ss);
}
return str.toString();
}
private void constructIndices(int B) {
indices = new int[B + B - 2];
int index = 0;
for (int i = 0; i < B; i++) {
indices[index++] = i;
}
for (int i = 0; i < B - 2; i++) {
indices[index++] = B - 2 - i;
}
}
}