Print given String in ZigZag Fashion

Problem Definition

Given a string and a number of lines $k$, print the string in zigzag form.

In zigzag, characters are printed out diagonally from top left to bottom right until reaching the $kth$ line, then back up to top right, and so on.

For example, given the sentence "thisisazigzag" and k = 4, you should print:

t     a     g
 h   s z   a
  i i   i z
   s     g

Solution

The solution to this problem would be to construct $k$ lines and print them.

Key Problem

Construction of each of the line is the key part of this problem. Each line would consist necessary characters from the $input\ string$ separated by required number of $spaces$. To construct each line we need to identify characters belonging to the line and number of spaces to be inserted after/before each of the characters.

Basic Algorithm

To construct each line,

1. Insert necessary number of spaces in the beginning of the line
2. Identify next character that belongs to this line and append to it
3. Append necessary number of spaces
4. Go to step 2, if there are more characters that belong to this line, otherwise print the line and move on to next line

Identify Size of spaces and Next Belonging Character

Assuming $0\ index$ based line numbers.

1. For $ith\ line$, number of spaces that starts the line $=\ i$
2. Index (say $index$) of first character that belong to $ith\ line = i$
3. Number of spaces that follows after a character depends upon whether we are moving $up\ or\ down$. For simplicity we can assume that at character on first line $i = 0$, we are always moving $down$, while for the last line $i = k-1$, we are always moving $up$. For other lines we will be alternatively moving $up$ and $down$ starting from moving down because initially we are moving down.

             If we are moving up,
                gapSize = 2 * i - 1
   
             Else if we are moving down,
                j = k - i - 1
                gapSize = 2 * j - 1
           

   
4. Index of next character will be $index = index + gapSize + 1$

Implementation

Following is the implementation as described above.

	import java.util.Scanner;
	public class ZigZag {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String input = "I am Lord Voldemort. Lord Voldemort is my past, my present and my future!!!"; //sc.next();
	System.out.print("Enter value of K: ");
	int K = sc.nextInt();
	System.out.println();
	for (int i = 0; i < K; i++) {
	StringBuilder sb = new StringBuilder();
	sb.append(new String(new char[i]).replace('\0', ' ')); // logic may be changed to create string of spaces
	int index = i;
	boolean up = i == K - 1; // for all lines except last, we start by moving down
	while(index < input.length()) {
	sb.append(input.charAt(index)); // append char
	int gapSize; // compute and append spaces
	if (up) {
	gapSize = 2 * i - 1;
	} else {
	int j = K - i - 1;
	gapSize = 2 * j - 1;
	}
	sb.append(new String(new char[gapSize]).replace('\0', ' ')); // logic may be changed to create string of spaces
	index += gapSize + 1; // index of next char for current line
	// set direction for next character
	if (i == 0) { // for top line always consider we are moving down
	up = false;
	} else if (i == K - 1) { // for last line always consider we are moving up
	up = true;
	} else { // for middle lines we alaternatively move down and up
	up = !up;
	}
	}
	System.out.println(sb.toString());
	}
	}
	}

view raw ZigZag.java hosted with ❤ by GitHub

Complexity

Ignoring the time complexity to construct string of empty spaces, the time complexity of this implementation is $O(n)$ because we go through each of the characters in the input string only once.

---

---

---