Short solution with explanation

  • 0

    First we build an array, which represents how many words we can put in a line for each word if that word is the 1st in the line (i.e. length[i] represents the number of words we can put in a line if sentence[i] is the leading word).

    After that, we continuously put words in each line, according to the total number of words we put currently, we can know what's the leading word in the next line. Then it is easy to compute the number of sentence we can fit.

    def wordsTyping(self, sentence, rows, cols):
            n = len(sentence)
            length = [0]*n
            for i in range(n):
                j = i              #sentence[i] is the leading word in this line
                cur = 0            #number of words we can fit in this line
                curlen = 0         #number of columns we use in the current line
                while (curlen+len(sentence[j]))<=cols:
                    cur += 1
                    curlen += len(sentence[j])+1
                    j = (j+1)%n         #next word we need to fit
                length[i] = cur
            start = 0     #the leading word in each line
            total = 0     #total number of words we have fit
            for i in range(rows):
                total += length[start]
                start = total % n
            return total/n

Log in to reply

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