{"id":1551,"date":"2020-07-01T09:31:45","date_gmt":"2020-07-01T09:31:45","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1551"},"modified":"2022-11-17T12:20:22","modified_gmt":"2022-11-17T12:20:22","slug":"zigzag-string","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/zigzag-string\/","title":{"rendered":"Zigzag String from the Character on Rows"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement (Simplified):<\/h3>\n

For a given string S<\/code> and number of rows R<\/code>, we have to arrange each character on rows in a vertical zigzag format, and then print values row-wise.<\/p>\n

<\/strong><\/u><\/a><\/p>\n

Can you guess the Time Complexity of this solution?<\/p>\n

Test Case<\/h4>\n
Input:\n1\n9 3\nprepbytes\n\nOutput:\npbsrpyeet\n\nExample:\nFor string 'prepbytes' and '3' rows, we arrange it in the following pattern.\n\np.......b.......s\n..r...p...y...e..\n....e.......t....\n\nNow we print this row-wise, so the answer will be 'pbsrpyeet'.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
1) To make a zigzag print, we print each character on the next row, and when row ends it goes back to 1st<\/sup> row. We repeat this pattern until the string ends.
\n2) As we can see pattern repeats once it reaches back to 1st<\/sup> row, So we divide the string into different parts and make a set of substrings for each repetition, each substring containing 2 x ( R - 1)<\/code> characters. For the above example, the above string converts into 3 substrings that are prep<\/code>, byte<\/code>, and s<\/code>.
\n3) Now we can see 1st<\/sup>  row contains 1st<\/sup>  element of each substring, and the last row contains a mid element of each substring.
\n4) For the rest of the elements, we notice every ith<\/sup>
\nrow contains ith<\/sup>  and ith<\/sup>  element in serial pattern.
\n5) Now we know all the patterns, we print them in serial order from every substring keeping notice that the current element does not go beyond the size of the string.<\/p>\n
Example<\/h3>\n
\n
    \n
  • Lets assume string S<\/code> to be ‘expertcoderprogram<\/code>‘ and number of rows R<\/code> be 4<\/code>.<\/li>\n
  • We can arrange this in this pattern :  <\/li>\n<\/ul>\n<\/blockquote>\n
    e . . . . . . c . . . . . r . . . . .  \n. x . . . . t . o . . . p . o . . . m  \n. . p . . r . . . d . r . . . g . a .  \n. . . e . . . . . . e . . . . . r . .  <\/code><\/pre>\n
    \n
      \n
    • We can see in each repition pattern there are    i.e.  characters. Hence there are 6<\/code> characters in each repetition pattern.<\/li>\n
    • As length of string S<\/code> is 18<\/code>, so there will be total 3<\/code> repetion patterns containing 6<\/code> elements each.  <\/li>\n
    • These repetions strings are ‘expert<\/code>‘, ‘coderp<\/code>‘ and ‘rogram<\/code>‘.<\/li>\n
    • Let length of each repetition string be N<\/code>.<\/li>\n
    • For every row we print:<\/li>\n<\/ul>\n<\/blockquote>\n
      \"\"<\/p>\n
      For<\/em><\/strong> 1st<\/sup> row: We print<\/em><\/strong> 1st<\/sup> element of each repetition string.<\/em><\/strong>  <\/p>\n
      See Graphic-1 Above<\/em><\/strong><\/p>\n
      \n
      Hence we print ecr<\/code>.<\/p>\n<\/blockquote>\n
      For<\/em><\/strong> 2nd<\/sup> row: We print<\/em><\/strong> 2nd<\/sup>  and<\/em><\/strong> (N-2+2)th<\/sup>` i.e.<\/em><\/strong> 3rd<\/sup> element of each repetition string.<\/em><\/strong>  <\/p>\n
      \n
      See Graphic-2 Above<\/em><\/strong> <\/p>\n
      Hence we print xtopom<\/code>.<\/p>\n<\/blockquote>\n
      For<\/em><\/strong> 3rd<\/sup>  row: We print<\/em><\/strong> 3rd<\/sup> and<\/em><\/strong> (N-3+2)th<\/sup> i.e.<\/em><\/strong> 5th<\/sup> element of each repetition string.<\/em><\/strong>  <\/p>\n
      See Graphic-3 Above<\/em><\/strong><\/p>\n
      \n
      Hence we print prdrga<\/code>.<\/p>\n<\/blockquote>\n
      For<\/em><\/strong>  4th<\/sup> row: We print<\/em><\/strong>  4th<\/sup> element of each repetition string.<\/em><\/strong>  <\/p>\n
      See Graphic-4 Above<\/em><\/strong><\/p>\n
      \n
      Hence we print eer<\/code>.<\/p>\n<\/blockquote>\n
      Solutions<\/h3>\n\t\t\t\t\t\t