A 10-lines one-pass o(n)-time o(1)-space accepted solution with detailed explantation


  • 43
    T

    The distribution of the elements is period.

    P   A   H   N
    A P L S I I G
    Y   I   R
    

    For example, the following has 4 periods(cycles):

    P   | A   | H   | N
    A P | L S | I I | G
    Y   | I   | R   |
    

    The size of every period is defined as "cycle"

    cycle = (2*nRows - 2), except nRows == 1.
    

    In this example, (2*nRows - 2) = 4.

    In every period, every row has 2 elements, except the first row and the last row.

    Suppose the current row is i, the index of the first element is j:

    j = i + cycle*k, k = 0, 1, 2, ...
    

    The index of the second element is secondJ:

    secondJ = (j - i) + cycle - i
    

    (j-i) is the start of current period, (j-i) + cycle is the start of next period.

    string convert(string s, int nRows) {
            if(nRows <= 1) return s;
            string result = "";
            //the size of a cycle(period)
            int cycle = 2 * nRows - 2;
            for(int i = 0; i < nRows; ++i)
            {
                for(int j = i; j < s.length(); j = j + cycle){
                   result = result + s[j];
                   int secondJ = (j - i) + cycle - i;
                   if(i != 0 && i != nRows-1 && secondJ < s.length())
                       result = result + s[secondJ];
                }
            }
            return result;
        }

  • 4
    T

    The following is python version:

     def convert(self, s, numRows):
            if numRows<=1: return s
            cycle, slen, res = numRows*2 - 2, len(s), ""
            for i in xrange(numRows):
                for j in xrange(i, slen, cycle):
                    res += s[j]
                    secondJ = (j - i) + cycle - i
                    if (secondJ-j) % cycle != 0 and secondJ < slen:
                        res += s[secondJ]
            return res

  • 0
    Y

    Nice idea! But I think maybe you can use StringBuffer because String in Java is immutable and it may cost some time for the "+" operation.


  • 2
    K

    How is it 'O(1) space'? You accumulate the result in a separate string, so it's actually O(len(s)).
    It may be possible to devise an in-place algo in the same vein as used for 'rotate array'.


  • 0
    T

    u are right. But the result is output. Usually the space does't consider the output.


  • 4
    R

    edit from your code,4ms

    public String convert(String s, int nRows) {
        if(nRows <= 1) return s;
        char[]c=s.toCharArray();
        char[]result=new char[c.length];
        int r=0;
        //the size of a cycle(period)
        int cycle = 2 * nRows - 2;
        for(int j = 0; j < c.length; j = j + cycle){
            result[r++]=c[j];
        }
        for(int i = 1; i < nRows-1; ++i)
        {
            for(int j = i; j < c.length; j = j + cycle){
               result[r++]=c[j];
               int secondJ = (j - i) + cycle - i;
               if(secondJ < c.length )
                   result[r++]=c[secondJ];
            }
        }
        for(int j = nRows-1; j < c.length; j = j + cycle){
            result[r++]=c[j];
        }
        return String.valueOf(result);
    }
    

  • 0
    R

    very clear idea.i like it.


  • 0
    H

    C Version

    char* convert(char* s, int numRows) {
        int slen = strlen(s) ;
    
        if(numRows <= 1) return s;
        if(s == NULL) return s;
        if(slen <= 2) return s;
        char*ret_s = malloc(slen+1);
        int ith_2 = 0;
        int ret_idx = 0;
        int n = 0;
        int items_per_round = numRows*2 -2;
        int final_row = numRows - 1;
        while(n < numRows) {
            for(int ith = n; ith < slen; ith += items_per_round) {
                ret_s[ret_idx++] = s[ith];
                ith_2 = ith +  items_per_round - (n << 1);
                if(ith_2 < slen && n!=0 && n!= final_row) {
                    ret_s[ret_idx++] = s[ith_2];
                }
            }
            n++;
        }
        ret_s[ret_idx] = '\0';
        return ret_s;
    }
    

  • 0
    C

    how could it's space complixity be o(1) ? the space you used is according to the string's length


  • 0
    Z

    @yy.zhang it is string ,not String


Log in to reply
 

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