O(n) time complexity


  • 0
    X
    char* convert(char* s, int numRows) {
        int len = strlen(s),i=1,n=1,m,r,p=0,sp=2*numRows-2;
        char *t = (char *) malloc(sizeof(char)*(len+1));
        if(numRows == 1) sp = 1;
        m = len/sp;
        r = len%sp;
        if(r != 0) m++;
        for(; i<=len; i++) {
                if(n == 1 || n == numRows) *(t+i-1) = *(s+n+sp*(i-p-1)-1);
                else *(t+i-1) = *(s+n+(sp-2*n+2)*(i-p-1)+(i-p-1)/2*(4*n-sp-4)-1);
                if((n == 1 &&  i < m) || (n != 1 && i-p < 2*m-1) || (i-p == 2*m-1 && numRows-n < r-numRows+1)) continue;
                if((i-m-p)%m == 0 || (i-m-p)%(m-1) == 0){
                        p = i; n++;
                }
        }
        *(t+i) = '\0';
        return t;
    }
    

    I do not know why show me Runtime Error.

    this is error message, Last executed input:
    "hsscheopebsyzagbpcwcbmvuwmrgpixwarajvpycssartgskkqomcjiaxzgnhfljxmsudswvlxogfgsqygebsm", 68

    and it can output on my computer, "hsscheopebsyzagbpcwcbmvuwmrgpixwarajvpycssartgskkqmosmbcejgiyaqxszggfnghofxlljvxwmssdu"

    I really hope someone can help me! best wish to you!


  • 0
    U

    class Solution {
    public:
    string convert(string s, int numRows) {
    int i,j,k,y=0,t;
    if(numRows<2) return s;
    string ret;
    const int stp=2*(numRows-1);
    const int sta=2*numRows-2;
    const int len=s.size();
    ret.resize(len);
    for(k=0;k<len;k+=stp)
    ret[y++]=s[k];
    for(i=1;i<numRows-1;i++)
    {
    k=y;
    for(j=i,t=k;j<len;j+=stp,y++) ret[t]=s[j],t+=2;

    		for(j=sta-i,t=k+1;j<len;j+=stp,y++)
    		    ret[t]=s[j],t+=2;
    	}
    	for(k=numRows-1;k<len;k+=stp) ret[y++]=s[k];
    	return ret;
    }
    

    };


Log in to reply
 

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