ZigZag Conversion

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".

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

OK, I actually saw a similar question before when I was tutoring a student learning a 100 level class. It was in python and instead of ZigZag, it was called something about building fence blocks. I know this provides no info for solving this problem to whoever is reading this, but I’m just trying to make a point that whatever we’ve done may help us in the future in different ways. So let’s keep trying out new things in our lives 🙂

A good way to solve this question is to play with the example.

Example 1:  “PAYPALISHIRING” and 3

To create the ZigZag version, we go through “PAY”, then “P”, then “ALI”, … till the end. That is to say:

  1. scan and process 3 characters
  2. scan and process 1 character
  3. and repeat the first two steps till the end

Example 2: “PAYPALISHIRING” and 4

To create the ZigZag version, we go through “PAYP”, then “AL”, then “ISHI”, … till the end. That is to say:

  1. scan and process 4 characters
  2. scan and process 2 characters
  3. and repeat the first two steps till the end

Now you can try more examples, but based on these two examples, we can at least generalize the following:

  1. scan and process nRows characters
  2. scan and process nRows – 2 characters
  3. repeat the first two steps till the end

Here nRows have to be larger than 1. If nRows equals 1, we can simply just return the original string. 

OK, now how do we process those characters in step 1? Look at the following figure, we see three rows. The first character P is on row 1, A on row 2 and Y on row 3. Each character processed in step 1 ended up in different places. Well, this indicates that we may need nRows number of containers to store the characters.

P   A   H   N
A P L S I I G
Y   I   R

What about the characters in Step 2? First of all, we have an order here. Once we are done with characters in the step 1, we should somehow notify the program that we are now in step 2. There’s no difference of how we process these characters between step 1 and 2, except that we should think about in which container we should put these characters.

Say we have nRows containers labeled as 0 to nRows – 1. So the characters in step 1 should be put into container_0 to container_nRows-1 one by one in this order. For those in step 2, they should be put into container_nRows-1-1 to container_1.

Since these are characters, we could use a StringBuilder object as a container. So, we got a basic plan now. We do need to think about some corner cases:

  • The string is null or is an empty string
  • nRows equals 1
  • nRows equals 2 (better to check for this than being sorry later)

And we also need to think about creating variables to indicate whether we are in step 1 or 2.

Code on github:

 

Enhanced by Zemanta
Advertisements
ZigZag Conversion

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s