包子小道消息@01/04/2020
2020这才刚来没几天,挺闹心呀
Leetcode solution 6: Zig Zag Conversion
Blogger:https://blog.baozitraining.org/2020/01/leetcode-solution-6-zigzag-conversion.html
Youtube: https://youtu.be/62LdZVhwcMg
博客园: https://www.cnblogs.com/baozitraining/p/12052398.html
B站: https://www.bilibili.com/video/av79569155/
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 s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Problem link
You can find the detailed video tutorial here
It's a very good implementation problem, by simply simulating each character in the string to each row, it would take extra O(N) space to hold up the array where N is the string size. However, there is definitely a difference between a good and poor implementation.
There is also a math formula we can use, please see attached pdf for solutions.
1 public String convertSimulation(String s, int nRows) {
2 if (s == null || s.length() == 0 || nRows <= 0) {
3 return "";
4 }
5
6 if (nRows == 1) {
7 return s;
8 }
9
10 int size = s.length();
11 List<StringBuilder> buckets = new ArrayList();
12
13 for (int i = 0; i < nRows; i++) {
14 buckets.add(new StringBuilder());
15 }
16
17 int i = 0;
18 int index = 0;
19 boolean fromTopToBottom = true;
20 while (i < size) {
21 char c = s.charAt(i);
22
23 if (fromTopToBottom) {
24 if (index == nRows - 1) {
25 fromTopToBottom = false;
26 buckets.get(index).append(c);
27 index--;
28 } else {
29 buckets.get(index).append(c);
30 index++;
31 }
32 } else {
33 if (index == 0) {
34 fromTopToBottom = true;
35 buckets.get(index).append(c);
36 index++;
37 } else {
38 buckets.get(index).append(c);
39 index--;
40 }
41 }
42 i++;
43 }
44
45 String res = "";
46 for (StringBuilder sb : buckets) {
47 res += sb.toString();
48 }
49
50 return res;
51 }
Time Complexity: O(N) where N is the string size
Space Complexity: O(N) since we used an extra array to store each character in the string
1 public String convertSimulationOptimizedImplementation(String s, int nRows) {
2 if (s == null || s.length() == 0 || nRows <= 0) {
3 return "";
4 }
5
6 if (nRows == 1) {
7 return s;
8 }
9
10 int size = s.length();
11 // directly allocate a string builder array
12 StringBuilder[] buckets = new StringBuilder[nRows];
13 for (int i = 0; i < nRows; i++) {
14 buckets[i] = new StringBuilder();
15 }
16
17
18 int i = 0;
19 int index = 0;
20 boolean fromTopToBottom = true;
21 while (i < size) {
22 char c = s.charAt(i);
23 buckets[index].append(c);
24 index += fromTopToBottom ? 1 : -1;
25
26 if (index == nRows - 1 || index == 0) {
27 fromTopToBottom = !fromTopToBottom;
28 }
29
30 i++;
31 }
32
33 String res = "";
34 for (StringBuilder sb : buckets) {
35 res += sb.toString();
36 }
37
38 return res;
39 }
Time Complexity: O(N) where N is the string size
Space Complexity: O(N) since we used an extra array to store each character in the string