16ms and O(n) c++ soution. Fastest in C++

  • 2

    Given an index i of string s, if we can calculate the index of the new string, then it's an O(n) solution. Here is how I do it. Let's see the code first.

    class Solution {
        string convert(string s, int numRows) {
            if(numRows <= 1)
                return s;
            int period = numRows * 2 - 2;// this constant is very important.
            string ret;
            for(int i = 0; i < numRows; i++)//iterate by row number
                int n = 0;
                for(int j = i; j < s.size();)
                    ret += s[j];
                    /* the following 4 lines gives the next j should be */
                    if(i == 0 || i == numRows - 1)
                        j += period;
                        j = (++n) * period - j;
            return ret;

    what really confuses me at first is the relation between row number and the letters should be in the row. I draw a graph, simply explain it. Take the PAYPALISHIRING for example, and row = 4;
    if you can't see the picture, link is here 链接在这里 or here
    screenshot in baidu netdisk
    Now, it's brief. if row is 0 or numRows - 1, n*6+row the next position; if it's not, n*6-row is the next position, where n is an counter, from 1 to value which it can grow but won't make j >= s.size()

  • 0

    I can't see pictures, what can i do?

Log in to reply

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