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

.**Understand the problem:**

The crux of the problem is to understand what is the "zigzag" format. We can use examples to illustrate this. For number of rows is 2,

0 A C

1 B D

For nRows = 3,

0 A E

1 B D F

2 C G

For nRows = 4

0 A G

1 B F H

2 C E I

3 D M

It is actually easier to understand the problem putting the characters into a mesh grid.

**Solution:**

We can divide the zigzag format into several zigzags. For nRows = 4,

1 | 7 |

2 6 | 8 12 |

3 5 | 9 11 |

4 | 10 |

So each zigzag has number of nRows * 2 - 2 elements.

For each zigzag, the first row and last row, the distance between two indices is nRow * 2 - 2. For example, distance between 1 and 7 is 6, distance between 4 and 10 is 6, which can be calculated as 4 * 2 - 2 = 6.

For each other rows from 1 to nRows - 2, the distance between two indices is (nRows - i - 1 ) * 2 = nRows * 2 - 2 - 2 * i. Note that the distance between A to B is defined as [A, B). Also note that for each zigzag, there are at most two elements in a row.

Based on the analysis above, we can come up the solution below:

**Code (Java):**

public class Solution { public String convert(String s, int nRows) { if (s == null || s.length() == 0 || nRows <= 0) return ""; if (nRows == 1) return s; StringBuilder sb = new StringBuilder(); //non-thread safe int size = 2 * nRows - 2; // number of elements for each zigzag for (int i = 0; i < nRows; i++) { for (int j = i; j < s.length(); j += size) { sb.append(s.charAt(j)); if (i != 0 && i != nRows - 1 && (j + size - 2 * i) < s.length()) { sb.append(s.charAt(j + size - 2 * i)); } } } return sb.toString(); } }

**Discussion:**

The time complexity is O(n) since we only traverse the string once. The space complexity is O(n) as well since we performed out-of-place transform.

**Summary:**

The crux of this problem is to convert the indices from zigzag-major to row-major. Be familiar with the zigzag-major format.

## No comments:

## Post a Comment