This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/zigzag-conversion-problem/.
Problem
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)Example
P A H N A P L S I I G Y I RAnd 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".Solution
Method 1 - Use list to save the substrings
A straightforward solution is to actually build up the zigzag character matrix and read the matrix into a string.
Here is the basic algo:
- Maintain down boolean which tells whether you are going up or down in zig zag order.
- As soon as rows = 0 means you need to go down now and as soon as rows = nRows - 1 you need to go up now
- Just keep on doing this until whole string is exhausted
- Using StringBuilder list/array to store elements in zig zag order and in the end just append all characters from each StringBuilder to return output.
import java.util.ArrayList;
public class Solution {
public String convert(String s, int nRows) {
if(s == null || s.length() <= 1 || nRows <= 1){
return s;
}
ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();
for(int i = 0; i < nRows; i++){
list.add(new StringBuilder());
}
int i = 0;
boolean down = false;
int row = 0;
while(i < s.length()){
list.get(row).append(s.charAt(i));
if(row == 0){
down = true;
}else if(row == nRows - 1){
down = false;
}
if(down){
row++;
}else{
row--;
}
i++;
}
i = 0;
StringBuilder output = new StringBuilder();
while( i < list.size()){
output.append(list.get(i).toString());
i++;
}
return output.toString();
}
}
Though time complexity is good O(n), but the space is complexity is O(nRows*Max_column_in_a_row) = O(n)
Method 2 - Append the character on the fly
Another way is to calculate the corresponding index on the fly and append the character into a string.Take
convert("PAYPALISHIRING", 4) as an example. The matrix will look as follows :
P I N A L S I G Y A H R P I
which can be expended as below (You will see why we rewrite like this soon.).
P I N A S G Y H P I A R L I
Some useful properties:
- For any full columns, the odd ones have nRows characters, even ones have (nRows - 2) characters.
- For the first and last rows, we read one single character from each expended column;
- For the rest of rows, we read two characters, one from top part and one from bottom part, from each expended column.
- One edge case is that nRows = 1, where (nRows*2 - 2) becomes 0. In this case, we should simply return the original string.
public String convert(String s, int nRows) {
if (nRows == 1) return s;
StringBuilder ss = new StringBuilder();
int n = nRows + nRows - 2;
// rest rows
for (int i = 0; i < nRows; ++i) {
int cur = i;
while (cur < s.length()) {
ss.append(s.charAt(cur));
cur += n;
if (i > 0 && i < nRows - 1 && (cur - i - i) < s.length()) {
ss.append(s.charAt(cur - i - i));
}
}
}
return ss.toString();
}
Thanks.
Reference
http://www.params.me/2014/04/leetcode-zigzag-conversion-in-java.html
http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html
https://leetcode.com/problems/zigzag-conversion/