PROBLEM STATEMENT
This problem is from Leetcode – Zigzag Conversion. The problem statement in short is given below:
Write a string in a zigzag pattern on numRows rows, then read line-by-line to create a new string.
SOLUTION
FIRST APPROACH
public String convert(String s, int numRows) {
if( numRows < 2) {
return s;
}
String zigzag = "";
int numCols = s.length();
String[][] strMatrix = new String[numRows][numCols];
boolean allRows = true;
int charIdx = 0;
int diag = numRows-2;
// remove all the null values
initiateMatrix(strMatrix, numRows, numCols);
for(int col=0; col<numCols; col++ ) {
if(diag == 0) {
allRows = true;
diag = numRows-2;
}
if(charIdx > s.length()-1) {
printMatrix(strMatrix, numRows, numCols);
break;
}
// populate all rows of this column
if(allRows) {
for(int row=0; row<numRows && charIdx < s.length(); row++) {
strMatrix[row][col] = Character.toString(s.charAt(charIdx));
charIdx++;
}
allRows = false;
}
else {
strMatrix[diag--][col] = Character.toString(s.charAt(charIdx));
charIdx++;
}
} // endfor
// now read the matrix to return the required string
for(int row=0; row<numRows; row++) {
for(int col=0; col<numCols; col++ ) {
zigzag = zigzag + strMatrix[row][col] ;
}
}
return zigzag;
}
// initiate the matrix with empty string
private void initiateMatrix(String strMatrix[][], int numRows, int numCols) {
for(int row=0; row<numRows; row++) {
for(int col=0; col<numCols; col++ ) {
strMatrix[row][col] = "";
}
}
}
// print the given matrix
private void printMatrix(String strMatrix[][], int numRows, int numCols) {
for(int row=0; row<numRows; row++) {
for(int col=0; col<numCols; col++ ) {
System.out.print( strMatrix[row][col] + "\t");
}
System.out.println("");
}
}You can checkout he code from Github here: Zigzag conversion – First Approach.
PERFORMANCE ANALYSIS
| COMPLEXITY | O (N2) |
SECOND APPROACH
public String convert(String s, int numRows) {
if( numRows < 2) {
return s;
}
StringBuilder zigzag = new StringBuilder();
StringBuilder[] rows = new StringBuilder[numRows];
for(int i=0; i<numRows; i++) {
rows[i] = new StringBuilder();
}
boolean allRows = true;
int diag = numRows-2;
int numCols = s.length();
int rowIdx = 0;
for(int charIdx=0; charIdx<numCols; charIdx++ ) {
if(diag == 0) {
allRows = true;
diag = numRows-2;
}
if(allRows) {
// populate all rows of this column
rows[rowIdx] = rows[rowIdx].append(Character.toString(s.charAt(charIdx)));
rowIdx++;
if(rowIdx == numRows) {
allRows = false;
rowIdx = 0;
}
}
else {
rows[diag] = rows[diag].append(Character.toString(s.charAt(charIdx)));
diag--;
}
} // endfor
// now read the matrix to return the required string
for(int i=0; i<numRows; i++) {
zigzag = zigzag.append(rows[i]);
}
return zigzag.toString();
}You can checkout the code from Github here – Zigzag Conversion – Second Approach.
PERFORMANCE ANALYSIS
| RUNTIME | 6 ms | Beats 36.16 % |
| MEMORY | 45.46 MB | Beats 36.67 % |
| TIME COMPLEXITY | O (N) |