Simple solution after finding the rule in ZigZag Conversion problem


  • 0
    H

    This is very simple as long as we find the rule.

    when numRows=3, the index for each position in the string s would be:
    1 5 9
    2 4 6 8 10
    3 7 11
    So the output index from string s for each row would be:
    row0= [0:4:end]
    row1= [1:2:end]
    row2= [2:4:end]

    when numRows=4, the index for each position in the string s would be:
    1 7 13 19
    2 5 8 11 14 17 20
    3 6 9 12 15 18 21
    4 10 16 22

    So the output index from string s for each row would be:
    row0=[0:6:end]
    row1=[1:3:end]
    row2=[2:3:end]
    row3=[3:6:end]

    So we can easily find the rule, which would be for numRows, we will have N_loop items for each loop (a vertical line and a cross line), where N_loop = numRows + (numRows-2). Meanwhile, for the rows on top or bottom, the repeated index would be N_loop because there is no repetition between them, while for rows in middle, the repeated index would be (numRows-1).

    So the output index from string s for each row would be:
    row0=[0:N_loop:end]
    row1=[1:(numRows-1):end]
    row2=[2:(numRows-1):end]
    ...
    row numRows-1=[numRows-1:N_loop:end]

    Python implementation will be:

    class Solution(object):
        def convert(self, s, numRows):
            """
            :type s: str
            :type numRows: int
            :rtype: str
            """
            new_s = [];
            Nloop = numRows + (numRows-2);
            #row 1:
            idx = 0;
            while (idx<len(s)-1):
                new_s.append(s[idx]);
                idx +=Nloop;
            # middle rows
            for r in range(1,numRows-1):
                idx = r;
                while (idx<len(s)-1):
                    new_s.append(s[idx]);
                    idx +=numRows-1;
            #last rows
            idx = numRows-1;
            while (idx<len(s)-1):
                new_s.append(s[idx]);
                idx +=Nloop;
            return new_s;

Log in to reply
 

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