What is a better solution for a changed zigzag printing?

Consider the following transformation on a string. Given as an input a number of rows and a string, write that string in a zigzag back and forth across the rows. For example, given input

Please convert me to a customized zigzag printing format

with three rows, we would write the string in a zigzag like this:

P   s   n   t   o   s   i   z   a   i   n   r
 l a e o v r m t a u t m z d i z g r n i g o m t
 e   c   e   e   c   o   e   g   p   t   f   a

(please dont edit this print out, this is required output, it is not a real zigzag, it is a customized zigzag)

Finally, we concatenate the contests of each row together to get the resulting string

Psntosizainrlaeovrmtautmzdizgrnigomteceecoegptfa

I have a sketch of an algorithm for this problem that I've written out in pseudocode here:

it is asking about the relationship between {index} and {output row and  col}
Def:
  down = false;
  up = false; 
  r=0;
  c=0;
  char[][] output; 
there are three cases here:
case 1: 
  index % 4 == 0, it is the beginning of a down printing
  r = 0;
  output[r][c] = in.charAt(index);
  c++;
  down = true; up = false;

case 2:
  index%4 != 0 && down = true;
  r = ind开发者_如何学运维ex % 4;
  output[r][c] = in.charAt(index);
  if( r == 2){ up = true; down = false; c++;}  // when come to the last row of a down formatting

case 3:
  index%4 != 0 && up == true;
  r = 4- index%4;
  output[r][c] = in.charAt(index);
  c++;

For a general solution, i can replace 4 as nRows+1;

While I think this works, I'm not too happy with it. Does anyone have a clearer or faster algorithm for solving this problem?

---

One observation that might make this problem much easier to solve is this following: Suppose that you have a row count of 3 and want to keep zigzagging across the rows distributing the characters. Then if you cycle over four characters, you would add them to rows 1, 2, 3, and 2 before repeating this pattern. With a row count of five you'd visit rows 1, 2, 3, 4, 5, 4, 3, and 2 before repeating this pattern. More generally, if you have a row count of k, then the set of rows to distribute the characters into follows the pattern 1, 2, 3, ..., k, k - 1, k - 2, ..., 2, which has length 2k - 2.

Given this observation, you might make the code much cleaner by precomputing a table containing this cycle along with the length of that cycle. Once you have this table, you can then cycle across the characters, keep track of which character you are on. When you're on the nth character, you would index into the table at position n mod k, then distribute the character into that row.

In pseudocode (using one-based indices):

rowTable = new array of ints length 2k - 2
for i = 1 up to k:
    rowTable[i] = i
for i = 2 up to k - 1:
    rowTable[(2k - 1) - (i - 2)] = i

resultRows = new array of strings of length k

for i = 1 up to the length of your string:
    Append the current character to resultRows[rowTable[i mod k]]

Concatenate all the entries of resultRows

This approach doesn't require you to hard-code in all of the different cases into a switch statement, which means that it can handle arbitrary k instead of just k = 3. Moreover, it's very fast; the runtime is O(n + k), where n is the length of the string and k is the number of rows.

Hope this helps!

---

What do you think of this one. Original string is s -copy chars from 0 to rows-1 in a string say str

str[rows]=some impossible to occur in d original string character , like -1

-copy reverse chars from s[r] to s[2r-3] into str

str[2r-2]=some impossible to occur in d original string character, -1

repeat until length is covered for these two steps, one by one.

In string str, take up every character at rows location, i.e. str[0],str[rows],str[2rows]... skipping over where str[rows] is -1. Repeat this step until length of str.