Share simple C++ solution


  • 107
    E

    The problem statement itself is unclear for many. Especially for 2-row case. "ABCD", 2 --> "ACBD". The confusion most likely is from the character placement. I would like to extend it a little bit to make ZigZag easy understood.

    The example can be written as follow:

    1. P.......A........H.......N
    2. ..A..P....L..S....I...I....G
    3. ....Y.........I........R

    Therefore, <ABCD, 2> can be arranged as:

    1. A....C
    2. ...B....D

    My simple accepted code:

    string convert(string s, int nRows) {
        
        if (nRows <= 1)
            return s;
    
        const int len = (int)s.length();
        string *str = new string[nRows];
    
        int row = 0, step = 1;
        for (int i = 0; i < len; ++i)
        {
            str[row].push_back(s[i]);
    
            if (row == 0)
                step = 1;
            else if (row == nRows - 1)
                step = -1;
    
            row += step;
        }
    
        s.clear();
        for (int j = 0; j < nRows; ++j)
        {
            s.append(str[j]);
        }
    
        delete[] str;
        return s;
    }

  • 0
    W

    Even though you handle the problem by using string array, the code is still pretty intuitive, good job


  • 1
    S

    it is pretty! it is quite intuitive. you can using vecotr<string> instead of using string array! it is a good job anyway!


  • 0
    5

    well done! Thanks for sharing


  • 2
    U

    I cannot understand the question for quite a long time. Thank you for your explination!


  • 0
    Q

    your solution is very nice!


  • 0
    K

    Test your solution with a longer string you will see the result is wrong! such as: convert("PAYPALISHIRINGKLKJHRTUIGFDRRF", 5);


  • 0
    K

    cool! the code is right.


  • 0
    H

    Thanks! Before reading your explaination, I have been inserting white spaces to various calculated locations in the original string then prepare to use (x, y) solving the problem. It turns out this is not a square or rectangle but just a ZigZag figure, no white space involved.


  • 3

  • 0
    A

    use numRows space and easy to understand ,while my answer search the math solution,not easy to understand ,but is interesting

    string convert(string s, int numRows)
    {
        int length = s.size();
        if(numRows <= 1 || length <= numRows)
            return s;
        string sZigzag;
        for(int iLineIndex = 0; iLineIndex < numRows; iLineIndex++)
        {
            int iRowIndex = iLineIndex;
            for(; iRowIndex < length; iRowIndex += 2 * (numRows - 1))
            {
                if(0 == iLineIndex || numRows - 1 == iLineIndex)
                    sZigzag = sZigzag + s[iRowIndex];
                else
                {
                    if(iRowIndex == iLineIndex)
                        sZigzag = sZigzag + s[iRowIndex];
                    else
                    {
                        sZigzag = sZigzag + s[iRowIndex - 2 * iLineIndex];
                        sZigzag = sZigzag + s[iRowIndex];
                    }
                }
            }
            if((iLineIndex > 0) && (iLineIndex < numRows - 1) && (iRowIndex - 2 * iLineIndex < length))
                sZigzag = sZigzag + s[iRowIndex - 2 * iLineIndex];
        }
        return sZigzag;
    }

  • 0
    N

    great! easy to understand.


  • 0
    N

    @enze98

    Why mine is so slow 72ms, compared to yours only 24ms? Is it because I'm using stringstream?

    class Solution {
    public:
        string convert(string s, int numRows) {
            
            if(1 == numRows || s.length() < numRows) {
                return s;
            }
            
            int len = s.length();
            // use numRows stringstream to hold temp data
            stringstream * ss = new stringstream[numRows];
            
            int row = 0, step;
            for(int j = 0; j < len; ++j) {
                ss[row] << s[j];
                
                if(0 == row) {
                    step = 1;
                } else if(numRows - 1 == row) {
                    step = -1;
                }
                
                row += step;
            }
            
            stringstream res;
            for(int k = 0; k < numRows; ++k) {
                res << ss[k].str();
            }
            
            delete[] ss;
            return res.str();
            
        }
    };
    

  • 0
    P

    Amazing! Although I can not speak English very well,i still say thanks to you.


  • 0
    E

    Thanks for your sharing!


  • 0
    V

    Very intutive solution and easy to understand. Thanks


  • 0
    S

    I did this solution but I was not able to test it on the site. I have tested on g++ and works perfectly.

    class Solution {
    public:
        string convert(string s, int numRows) {
            string ret(s.length(), ' ');
            if (numRows > 1)
            {
                    int step = (numRows - 1) * 2;
                    int counter = 0;
                    for (int j = 0; j < numRows; j++)
                    {
                        for (int i = j; i < s.length(); i = i + step)
                        {
                            ret[counter] = s[i];
                            ++counter;
                            int offset = step - j * 2;
                            if (offset > 0 && offset < step)
                            {
                                int pos = offset + i;
                                if (pos < s.length())
                                {
                                    ret[counter] = s[pos];
                                    ++counter;
                                }
                            }
                        }
                     }
            } else {
                    ret = s;
            }
            return ret;
        }
    };

  • 0
    L

    it's wonderful


  • 0
    R
    public:
        string convert(string s, int numRows) {
            int size = s.size();
            if ((size <= numRows) || (numRows == 1)) return s;
            
            int pitch = 2 * (numRows - 1);
            int rowMax = numRows - 1;
            string res;
            res.reserve(size);
    
            for ( int i = 0; i < numRows; i++) {
                int pos = i;
                int pitch1 = 2 * (rowMax - i);
                int pitch2 = pitch -pitch1;
                if ( pitch1 == 0) pitch1 = pitch;
                if ( pitch2 == 0) pitch2 = pitch;
    
                while ( pos < size){
                    res.push_back(s[pos]);    
                    pos += pitch1;
                    if (pos < size) {
                        res.push_back(s[pos]);
                    }
                    pos += pitch2;
                }            
            }
            return res;    
        }
    };```
    
    Took 12ms.

  • 0
    M

    In the problem description, the downward direction is always vertical, that is, the X coordinate is monotonically increasing but not at a constant rate with respect to the string index. Your code has it increasing at a constant rate (specifically, of 1) -- I'm not sure whether this makes the answer right or wrong, but it is different from other answers provided so far.


Log in to reply
 

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