PROBLEM 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)
1
2
3
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);
SOLUTION
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
class Solution {
public String convert(String s, int numRows) {
//edge case
if(numRows == 1) return s;
//length of the string
int n = s.length();
//number of jumps to go to next character in the next group
int jumps = 2*(numRows-1);
//ans
StringBuffer sb = new StringBuffer();
//first row
//it will start from index 0
int i = 0;
//while there are more characters, keep jumping 2*(numRows-1) times to go to next character in the next section of first row
while(i<n){
sb.append(s.charAt(i));
i += jumps;
}
//rows in between
//loop through the rows from [1, numRows-2]
for(int row=1; row<=numRows-2; row++){
//first character of row x, will be at index x
i = row;
//while there are more characters in the string
while(i<n){
//append the current character
sb.append(s.charAt(i));
//Important Part:
//the next character in this row will be present at: currentIndex + 2*(numRows-1) - (2 * currentRow)
int j = i + jumps - (2*row);
//check if that index is within the bounds
if(j<n){
sb.append(s.charAt(j));
}
//jump to the next character of the next group
i += jumps;
}
}
//last row (similar to first row)
//the first character will be at numRows-1
i = numRows-1;
while(i<n){
sb.append(s.charAt(i));
i += jumps;
}
return sb.toString();
}
}
ANOTHER WAY TO CODE
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
class Solution {
public String convert(String s, int numRows) {
//edge case
if(numRows == 1) return s;
//length of the string
int n = s.length();
//number of jumps needed to go to next character (of next group)
int jumps = 2 * (numRows-1);
//ans
StringBuffer sb = new StringBuffer();
//for each row
for(int r=0; r<numRows; r++){
//the first character position for row x will be at x index of the string
for(int i=r; i<n; i+=jumps){
//append the current character of the row
sb.append(s.charAt(i));
//if it's a middle row, we will need to get the second character
//it will be present at: currentIndex + 2*(numRows-1) - (2*currentRow)
if(r >= 1 && r <= numRows-2){
int secondCharPossiblePosition = i + jumps - (2*r); //this can possibly be out of bounds
//if it's within the bounds, append it
if(secondCharPossiblePosition < n){
sb.append(s.charAt(secondCharPossiblePosition));
}
}
//because of for loop increment condition, the next position will be current + 2*(numRows-1);
}
}
return sb.toString();
}
}