Python 108ms solution


  • 14
    V

    My solution was to preprocess the sentence in order to determine at each index of the sentence how many more words can fit in the column. After that I simply iterate through the rows and increment the total word count.

    class Solution(object):
        def wordsTyping(self, sentence, rows, cols):
            word_nums = self.preprocess(sentence, cols)          
            word_count = 0                
            for _ in xrange(rows):
                word_count += word_nums[word_count % len(sentence)]
            return word_count/len(sentence)
            
        # Preprocessing 
        def preprocess(self, sentence, cols):
            word_nums = [0] * len(sentence)
            word_ptr, word_sum = 0, 0
            word_len = len(sentence[0])
            for i, word in enumerate(sentence):
                while(word_sum + word_len <= cols):
                    word_sum += word_len
                    word_ptr += 1
                    word_len = len(sentence[word_ptr % len(sentence)]) + 1
                word_nums[i] = word_ptr - i
                word_sum -= (len(word) + 1)
            return word_nums
    

  • 5
    V

    I really like your solution, and just optimized it a little bit. The trick is that every row should have a fixed number of sentences (and fixed number of words represented as fixed_count) occupying a fixed chunk of space. So in the preprocessing, we don't need to start at the beginning of each row, but from the start.

    The code below runs 76 ms and beats 99.4%

    class Solution(object):
        def wordsTyping(self, sentence, rows, cols):
            words = [len(word) for word in sentence]
            nwords, slen = len(words), sum(words) + len(words) - 1
            fixed_count = (cols + 1) // (slen + 1) * len(words)
            start = cols + 1 - (cols + 1) % (slen + 1) if cols >= slen else 0
            
            counts = [fixed_count] * nwords
            for i in range(nwords):
                c = 0
                j = start
                while j + words[(i+c) % nwords] <= cols:
                    j += words[(i+c) % nwords] + 1
                    c += 1
                counts[i] += c
            
            words_count = 0
            for i in range(rows):
                words_count += counts[words_count % nwords]
            return words_count // nwords
    

Log in to reply
 

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