Should be straightforward O(N) solution in C++


  • 3
    T
    class Solution {
    public:
        string convert(string s, int nRows) {
            if(s.length() == 0 || 
                s.length()/nRows < 1 ||
                nRows == 1) 
            {
                return s;
            }
            int distance = 2*(nRows-1);
            string result;
            int offset = 0;
            for (int row = 0; row < nRows; row++)
            {
                for (int index = row; index < s.length(); index += distance)
                {
                    result+=s[index];
                    if (offset != 0 && index + distance - offset < s.length())
                    {
                        result+=s[index + distance - offset];
                    }
                }
                offset += 2;
                offset = offset % distance;
            }
            return result;
        }
    };
    

    The idea is, the first row and last row has no offset. Each element has a fixed difference of 2(nRows-1);
    For the rows in between, there is a incremental offset of 2;

    0       6       12    -> distance = 2(nRows-1) = 6 offset = 0
    1    5  7     11        -> offset =  distance - 2 = 4
    2  4    8  10            -> offset = distance -2 -2 = 2
    3       9                  -> distance = 2(nRows-1) = 6 offset = 0
    

    Easy to observe. There is a catch, that you need to add the offset element with previous regular element.
    5 follows 1, 4 follows 2. Otherwise, you will miss the tail if there is no vertical column in the end.Looks like a CS homework:)


  • 0
    M

    int length = s.length();
    if( length <= nRows)
    {
    return s;
    }
    if(nRows == 1)
    {
    return s;
    }

    char * newstring = new (nothrow) char[length+1];
    if( !newstring)
    {
        cout<<"error on allocate memory for new string"<<endl;
    }
    newstring[length] = 0;
    int newpos = 0;
    for( int i = 0; i < nRows; i++)
    {
        int col = 0;
        int pos = 0;
        while((pos = i + ((nRows-2)*2+2)*col) < length)
        {
            if( i > 0 && i < nRows -1 )
            {
                newstring[newpos++] = s[pos];
                if( pos + 2*(nRows-i-1) < length)
                    newstring[newpos++] = s[pos+2*(nRows-i-1)];
            }
            else
            {
                newstring[newpos++] = s[pos];
            }
    
            col++;
        }
    }
    return string(newstring);

Log in to reply
 

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