Expected output of ABCDE, 4


  • 3
    A

    Hi,
    In the Zig Zag problem the expected output for ABCDE,4 is given as ABCED but I feel that it should be AEBCD. Could someone help me with this? Can someone clarify how to deal with even and odd number of rows? My Approach to the question is to make a matrix of the positions and then "string" them together.
    So for example if the input is ABC,2 the matrix structure is expected to look like:

     0  1
    0 A C
    1 B <blank>
    

    Also in the example, PAYPALISHIRING,3 stated in the problem itself, can be visualized as

         0 1 2 3 4 5 6 
       0 P   A   H   N
       1 A P L S I I G
       2 Y   I   R
    

    My question is in the even columns (0 ,2,4 etc) the number of entries is fixed by the second argument of the problem. Whereas the entries in the odd columns(1,3 etc) is ambiguous to me. In the above example the first P is placed at location (1,1) the other slots are blank.

    If the same test case were to be modified as PAYPALISHIRING,4 How would the matrix look like?

         0 1 2 3 4 5 6 
       0 P ?  
       1 A ?
       2 Y ? 
       3 P ?
    

    Where would the next character come? Where would the blank spaces come? How is that decision made? Or is this a cumbersome approach?


  • 39
    S

    For ABCDE, 4, its zigzag pattern would like below:

    A
    B
    C E
    D
    

    Then, consider there are 4 strings, each line is a string, A B CE D, connect them one by one.
    So the output should be ABCED

    First of all, the blank here is use for good looking, make it looks like zigzag. When you generate the output, should ignore them.

    For PAYPALISHIRING,4, the matrix would like below, just ignore the index:

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

    and then you can treat each line as below, no blank:

    PIN
    ALSIG
    YAHR
    PI
    

    the output should be PIN+ALSIG+YAHR+PI=PINALSIGYAHRPI


  • 0
    A

    I could understand that from the answer, but then I want to understand how the pattern has been decided. Could you clarify that?


  • 0
    S

    I have updated my answer. Please have a look, if you still have question, just leave comment. :)


  • 0
    A

    Hi Shangrila, I updated my question. Hope you can help me find a solution now


  • 0
    S

    I have updated my answer.


  • 0
    A

    Hi Shangrila, In your answer,how do you decide the position of A (which is at 1,2) ? How can it be said that is placed next to Y (0,2) and not next to A(0,1) ? From your answer I can infer that "PINAASRGYLHIPI" can also be the solution (i switched the places of (A,L) and (R,I)


  • 0
    S

    You just go the whole string, from up to down then from down to up, it work as zig zag. If you switch (A, L) and (R, I), how does it look like a zigzag?


  • 0
    A

    what I meant by switch places was that A is at (1,2), L is at (2,1). Say, A is at (1,1) and L is at (2,2) it still would be a zig zag right?


  • 0
    S

    In this problem, it defines like that, go from up to down, then down to up. If switch it, it would be from down to up then up to down. However, it can be discussed during the interview process. But now, in our OJ, we have defined the principle, you should write your code follow it.


  • 0
    A

    oh! Now I get it. Thanks a lot Shangrila :)


  • 0
    T

    I think LeetCode admin should adapt this description - The description given in OJ is not clear.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.