Yet another C++ Implementation


  • 0
    P

    Just write down the zig-zag shape of the string from numRows=1,2,3,4,5,..., and then you will find that the pattern of the skip steps of each row is like:

    1. Each row skips every step = (2-1)*numRows element;
    2. Also, there will be an additional element fro row 2 to row numRows-1. The index of the additional element is the index of the current element plus (step - (i * 2))%step.

    Here is the code:

        string convert(string s, int numRows) {
            if (numRows == 1) return s;
            int step = numRows * 2 - 2;
            string out = s;
            int tail = 0;
            for (int i = 0; i < numRows; ++i) {
                int mid = (step - (i * 2))%step;
                // cout << mid << endl;
                int j = i;
                while (j < s.size()) {
                    out[tail++] = s[j];
                    // cout << s[j];
                    if (mid && j + mid < s.size()) {
                        out[tail++] = s[j+mid]; 
                        // cout << s[j+mid];
                    }
                    j += step;
                }
            }
            return out;
        }
    

Log in to reply
 

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