Share my O(1) space O(n) time C++ solution with detailed explanation


  • 2
    B

    You could visualize the zigzaged string as

    A ........
      B   D
        C   
    or
    A ......E
      B   D   F
        C 
    

    there are three cases;

    1. if zigzag to one row or string's length is less then numRows, then no replacement is needed
    2. replace first Row or last Row, since each round has only one element in first Row or last Row, the step is 2 * (numRows - 1) List item
    3. intermidate character in the slop downward or upward, the downward step is 2 * (numRows - 1 - i), the upward step is 2 *(i)

    So My code is

    class Solution {
    public:
        string convert(string s, int numRows) {
            if (numRows == 1 || s.size() <= numRows) return s;
            string res = s;
            size_t res_pos = 0;
            for(size_t i = 0; i < numRows; ++i){
                bool downward = true;
                for(size_t j = i; j < s.size();){
                    res[res_pos++] = s[j];
                    if (i == 0 || i == numRows - 1){
                        j += 2 * (numRows - 1);
                    } else {
                        j += 2 * (downward ? numRows - i - 1 : i);
                        downward = not downward;
                    }
                }
            }
            return res;
        }
    };

  • 0
    X

    Good code. One thing to point out here is that you don't need to specialize some codes for the first row since i=0, so the step size is 2 * (numRows - 1 - 0).


  • 0
    B

    thanks for your advice. I have updated my code to
    class Solution {
    public:
    string convert(string s, int numRows) {
    if (numRows == 1 || s.size() <= numRows) return s;
    string res = s;
    size_t res_pos = 0;
    for(size_t i = 0; i < numRows; ++i){
    bool downward = true;
    for(size_t j = i; j < s.size();){
    res[res_pos++] = s[j];
    if (i == 0 || i == numRows - 1){
    j += 2 * (numRows - 1);
    } else {
    j += 2 * (downward ? numRows - i - 1 : i);
    downward = not downward;
    }
    }
    }
    return res;
    }
    };


Log in to reply
 

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