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/