### Problem

The string `"PAYPALISHIRING"`

is written in a zigzag pattern on a given number of rows like this:

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

#### Examples:

### Solution

The problem is essentially of remapping indices to the known pattern. Given the number rows `n`

in the zigzag, it is easy to find that the number of characters in a single zigzag is `2n-2`

. Additionally, there is a one to one correspondence between the indices in each ordering, so with information of the zigzag size, there should be no problem traversing through and reassigning each character's indices in `O(n)`

.

Time complexity: `O(n)`

Space complexity: `O(n)`

Percentile: `98.12%`

public String convert(String s, int nRows) { if (s==null || s.length()==0) return ""; if (nRows < 2) return s; int N = s.length(); int n = 2*nRows-2; int idx = 0; StringBuilder sb = new StringBuilder(); for (int i=0; i<nRows; i++) { for (int j=i; j<N; j+=n) { sb.append(s.charAt(j)); if (i>0 && i<nRows-1 && j+n-2*i<N) sb.append(s.charAt(j+n-2*i)); } } return sb.toString(); }

## No comments:

## Post a Comment