Python 42 ms O(N^2) where N=len(sentence)


  • 0
    Y
    
    class Solution(object):
        def wordsTyping(self, sentence, rows, cols):
            """
            :type sentence: List[str]
            :type rows: int
            :type cols: int
            :rtype: int
            """
            word_lens=[len(s) for s in sentence]
            i,cur,L=0,0,len(word_lens)
            
            #column optimization
            res=((cols+1)/(L+sum(word_lens)))*rows
            cols=(cols+1)%(L+sum(word_lens))
            
            #row optimizatoin
            d={}
            rowoptimized=False
            
            while i<rows:
                j=0
                while j+word_lens[cur%L]+1<=cols:
                    j+=word_lens[cur%L]+1
                    cur+=1
                i+=1
                
                if not rowoptimized:
                    if cur%L not in d:
                        d[cur%L]=(i,cur/L)
                    else:
                        rowoptimized=True
                        idiff=i-d[cur%L][0]
                        resdiff=cur/L-d[cur%L][1]
                        res+=((rows-i)/idiff)*resdiff
                        i=rows-(rows-i)%idiff
            return cur/L+res
    
    

Log in to reply
 

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