Question
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".
Stats
| Frequency | 1 |
| Diffficulty | 3 |
| Adjusted Difficulty | 3 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Solution
Two ways to work out this problem.
Solution 1. Insert string s vertically into a 2d array, char by char. After this is finished, make the result string by reading the 2d array horizontally. See code 1 below.
Solution 2. Calculate and find out (in sequence) which char from s should be inserted into the result list. Then build the result list directly. See code 2 below.
My code
One. Fill in the whole string, then parse the result.
public class Solution {
public String convert(String s, int nRows) {
if (s == null || s.length() == 0 || nRows < 1) {
return "";
} else if (nRows == 1) {
return s;
}
int len = s.length();
int grpSize = nRows * 2 - 2;
int numGrp = (len - 1) / grpSize + 1;
String[][] array = new String[nRows][numGrp * 2];
// fill in string s into array, one group after another
int p = 0;
// for each group
for (int i = 0; i < numGrp; i++) {
// for each vertical index (left col), fill in one letter from s
for (int j = 0; j < nRows; j++) {
// if s is used up, break
if (p == len) {
break;
}
array[j][i * 2] = "" + s.charAt(p);
p++;
}
// for each vertical index (right col), fill in one letter from s
for (int j = nRows - 2; j > 0; j--) {
// if s is used up, break
if (p == len) {
break;
}
array[j][i * 2 + 1] = "" + s.charAt(p);
p++;
}
}
// now convert array[][] into final string and return answer
StringBuilder sb = new StringBuilder();
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if (array[i][j] == null || array[i][j].length() == 0) {
continue;
} else {
sb.append(array[i][j]);
}
}
}
return sb.toString();
}
}
Two. Pick the correct char and form the result string, and fill it in the result string.
public class Solution {
public String convert(String s, int nRows) {
if (nRows <= 1)
return s;
int eachPattern = 2 * nRows - 2;
int numPatterns = (s.length() - 1) / eachPattern + 1;
StringBuilder ans = new StringBuilder();
for (int j = 0; j < nRows; j++) {
for (int i = 0; i < numPatterns; i++) {
ans.append(find(s, eachPattern, i, j));
if (j != 0 && j != nRows - 1)
ans.append(find(s, eachPattern, i, 2 * (nRows - 1) - j));
}
}
return ans.toString();
}
private String find(String s, int eachPattern, int i, int j) {
// find (j)th element from (i)th pattern
int temp = eachPattern * i + j;
if (temp < s.length())
return s.substring(temp, temp + 1);
return "";
}
}