4ms C solution with explanation


  • 0
    M

    As always, once we identify a coherent pattern, the solution is simple. Quite sure that this problem can be solved in several different ways. One such solution is posted below:

    Consider the example given in the problem itself : "PAYPALISHIRING" with row number = 3. To convert this string to the new representation we essentially need an equation to map the old offsets to the new offsets.

    Such an equation to map these offsets can be easily identified once we recognize the sub-structure to this problem. For example, following strings represent the first two sub-structures.

    P
    A P
    Y

    A
    L S
    I

    All such sub-structures tend to share the same qualities. For example, 'A' is at the relative offset 1 from base 'P' and 'L' is at the relative offset 1 from base 'A'. Similarly 'Y' and 'L' are at offset 2. So this means that once we can identify these sub-structures we can sequentially scan them and generate the new representation.

    For example, base of all these substructures form the first four characters "PAHN". Second set is formed by the pairs of characters at the offset 1 from the base and at an offset 1 behind the base of the immediate next structure. For example, the character 'A' is offset 1 from P and next character 'P' is at an offset behind the base 'A' of the next sub-structure. If we follow this pattern, then we have the string "PAHNAPLSIIG". Now increment the offset to two and repeat the operation on all the substructures.

    Final converted string is "PAHNAPLSIIGYIR". Code with additional comments is provided below.

    /***
     Main Function
     ***/
    char * convert(char* s, int numRows)
    {
        int len, w = (numRows - 2) * 2 + 2, i, t1, t2, r = numRows;
        int cnt = (2 * r) - 3, c, j;
        char *ns;
    
        /* Maintain Sanity */
        if (!s || !r)
            return NULL;
    
        /* Get the length */
        len = strlen(s);
    
        /* If the number of rows less than two or is equal to or greater than
           length, then there is no scope for conversion */
        if ((r >= len) || (r < 2))
            return s;
    
        /* Allocate the buffer */
        ns = malloc(sizeof(char) * len);
        if (!ns)
            return NULL;
    
        /* First set of mapped characters are separated by the offset
           difference calculated by the equation (row - 2) * 2 + 2.
    
           0 1 2 3 4 5 6 7 8 9 10 11 12 13    < Old Offsets
           P A Y P A L I S H I R  I  N  G
           0       1       2         3        < New Mapped Offsets
    
           PAHN                               < Partially converted string
    
        */
        for (i = 0, j = 0; i < len; i += w, ++j)
            ns[j] = s[i];
    
        /* Subsequent characters can be derived by scanning towards the
           middle of these offset windows set by the above equation
    
           0 1 2 3 4 5 6 7 8 9 10 11 12 13    < Old Offsets
           P A Y P A L I S H I R  I  N  G
           0       1       2         3        < Boundary Offsets
           t1 <->  t2                         < Scan Window 0 - 4
                   t1 <->  t2                 < Scan Window 4 - 8
                           t1  <->   t2       < Scan Window 8 - 12
                                     t1       < Scan Window 12 -13
           ------------------------------------------------------
           0 4   5 1 6   7 2 8    9  3  10    < Offsets (Iteration 0)
           P A Y P A L I S H I R  I  N  G     < t1 + 1 & t2 - 1
    
           "PAHNAPLSIIG"                      < Partially converted string
    
           ------------------------------------------------------
           0 4 11 5 1 6 12 7 2 8 13 9  3  10    < Offsets (Iteration 1)
           P A Y  P A L I  S H I  R I  N  G     < t1 + 2 & t2 - 2
    
           "PAHNAPLSIIGYIR"                     < Final Converted String
        */
        for (i = 0, c = 1; i < cnt; i += 2, ++c)
        {
            /* Initialize the scan window boundaries */
            t1 = 0;
            t2 = t1 + w;
    
            /* Scan */
            while ((t1 < len) || (t2 < len))
            {
                /* If the character is valid, then swap */
                if ((t1 + c) < len)
                    ns[j++] = s[t1 + c];
    
                if ((t1 + c) != (t2 - c) && ((t2 - c) < len))
                    ns[j++] = s[t2 - c];
    
                /* Advance the scan window */
                t1 = t2;
                t2 = t2 + w;
            }
        }
    
        /* Return Converted String */
        memcpy(s, ns, len);
        free(ns);
        return s;
    }
    

Log in to reply
 

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