Python solution O(N) with picture to understand


  • 5
    X

    Hello guys,it's my first time to post my code and I'd like do something helpful to you :)

    At first, we think about this question. If we paint the characters in our paper one by one, for a certain length and numrows.the showing just like a saw
    0_1470974866774_1 (2).png
    In this picture, every line means a word of output string. and the formulation is about the index and which word the character belongs to.

    Secondly, we serialize every word to the left and we can draw a saw like this.0_1470974286263_2.png

    Thirdly,we map each character to wordlist[0->n-1], which means the character belongs to.
    For each s'index i, we can mod to (2n-2) for getting his position to certatin the belonging word.

    To certain which word one character belongs to,we should dicuss the different situtation. For the index i, when i<=(n-1), means the direction of i is up to down straightly. Oppositely, when i >(n-1), the i is down to up sideling. But, all we do is get the position of i , so we should do something to distinguish this.

    The code like this:

    p = i%(2*n-2) 
    if p>(n-1): 
    	p=(2*n-2)-p                
    else: 
    	p=p 
    

    Lastly, we statistics the word list and just output the result is fine.
    So, the code will be like this

    class Solution(object):
        def convert(self, s, numRows):
            """
            :type s: str
            :type numRows: int
            :rtype: str
            """
            if numRows==1:
        		return s
        	length=len(s)
        	wordlist=[""]*numRows
        	charclass=[0]*length
        	for i in range(length):
        		charclass[i] = i%(2*numRows-2)
        		if charclass[i] > numRows-1:
        			charclass[i]=2*numRows-2-charclass[i] 
        	for i in range(length):
        		wordlist[charclass[i]]+=(s[i])
        	return "".join(wordlist)
    '''
    

    It costs some time to think about the arrangement of the characters. But for one thing important is that when we get the length and numrows, the arrangement is settled.We just to find out the align and mapping information is fine.
    The algorithms time complexity is O(N) and space complexity is O(N) too.


  • 0
    C

    The space complexity will be O(N^2) ?

    At worst case, numRows = length / 2. In this condition, wordlist variable will cost (length/2) * (length/2-1), so the space complexity is O(N^2) ?

    Using string to save multi char, the space complexity is O(n), but not O(1)


Log in to reply
 

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