zigzag conversion in C


  • 0

    Example string:

    "hello,world!"

    when numsRows = 3, after convertion:

    h     o     r
    e  l  ,  o  l  !
    l     w     d
    

    show them in index formation;

    0     4     8
    1  3  5  7  9   11
    2     6     10
    

    we may find the index follow the rule below (take numRows as n)
    =>

    rows
    1         0                  a                    b
    2         1             a-1  a+1             b-1  b+1
    3         2         a-2      a+2         b-2      b+2
    .
    .
    n-1       n-2   a-(n-2)      a+n-2  b-(n-2)       b+n-2
    n         n-1                a+n-1                b+n-1
           (=a-(n-1))         (=b-(n-1))
    

    as shown n-1=a-(n-1), a+n-1 = b-(n-1) => a=2n-2, b= 4n-4
    so the top line is
    0 , 2(n-1), 2*2(n-1), 2*3*(n-1)...2*q*(n-1)

    =>
    rows:
    1        0(2*0*(n-1))                          2*1*(n-1)                   
    2        2*0*(n-1)+1               2*1*(n-1)-1 2*1*(n-1)+1
    3        2*0*(n-1)+2   2*1*(n-1)-2             2*1*(n-1)+2
    .
    .
    n-1      2*0*(n-1)+(n-1)  2*1*(n-1)-(n-1-1)    2*1*(n-1)+(n-1)
    n        2*0*(n-1)+n                           2*1*(n-1)+n
    

    for any Row r between 1 and n we can get
    r: r-1,2*(n-1)-(r-1),2*(n-1)+(r-1), 2*2*(n-1)-(r-1),2*2*(n-1)+(r-1), ......2*q*(n-1)-(r-1), 2*q*(n-1)+(r-1)

    so we just need

    int left, right;
    int len = strlen(s);
    int idx = 0;
    // row between 1 and n
    for (int row > 1; row < n; row++)
    {
            for(int j = 0, q = 1; j < len; j = 2 * q * (numRows - 1), q++)
            {
                left = j - (row - 1); 
                right = j + (row - 1); 
                //  we start j from 0, then we got left < 0, we discard it
                if (left >= 0 )
                {
                    ret[idx] = s[left];
                    idx++;
                }
                // right should not big than len
                if(right < len)
                {
                    ret[idx] = s[right];
                    idx++;
                }
                
            }
    }
    

    the above method have three problems not solved;

      1. how to deal with row 1 and row n
      1. if n=1, it will infinitely loops, because j always zero.
      1. if j < len the chars after j+(n-1) will discard like below
    0              j               j+2*(n-1)(not in for loop because bigger than len)
    1              j+1
    2              j+2       j+n+1  <- index = len-1 end of string
    .                    j+n
    n-1            j+n-1
    

    when it comes to 1 we find that its left == right
    when it comes to n we find that its left == last j’s right.
    so we just discard right when it equals left and discard left when it equal last j‘s right. then it solved.
    as problem 2. we can just return string s when n = 1.
    as problems 3, we can change j < len to j < len + 2*(n-1). then discard its left when left ,right > len.
    then it solved.
    the final code in c below.

    char *convert(char *s, int numRows)
    {
        char *ret = NULL;
        int len = strlen(s);
        int idx = 0;
        int left, right;
        ret = (char *)malloc(sizeof(char) * (len + 1));
        if(numRows == 1) 
        {
            strcpy(ret, s);
            return ret;
        }
        for(int i = 1; i <= numRows; i++)  // row loop
        {
            for(int j = 0, q = 1; j < len + 2 * (numRows - 1); j = 2 * q * (numRows - 1), q++)
            {
                left = j - (i - 1); 
                right = j + (i - 1); 
                if (left >= 0 && left != right - 2 * (numRows - 1) && left < len)
                {
                    ret[idx] = s[left];
                    idx++;
                }
                if(right < len && right != left)
                {
                    ret[idx] = s[right];
                    idx++;
                }
                
            }
        }
        ret[idx] = '\0';
        return ret;
    }
    

Log in to reply
 

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