python solution of repeat pattern with comments


  • 0
    S

    Obviously, we only care about the length of words in the sentence. As a result, we need three variable to represent the current status: current_row, current_col and the index of current word in the sentence.

    We store the pattern each time we see c == 0 and once we see a pattern again, we can simply jump to the end of the loop with some math.

    class Solution(object):
        def wordsTyping(self, sentence, rows, cols):
            sentence = map(len, sentence)
            if any(map(lambda x: x > cols, sentence)):
                return 0
                
            # current_row, current_col, current_word_in_sentence
            r, c, s = 1, 0, 0
            res = 0
            # store the repeat pattern
            pattern = {}
    
            while r <= rows:
                if sentence[s] > cols - c:
                    # cannot fit
                    r += 1
                    c = 0
                if c == 0:
                    if s not in pattern:
                        # store the pattern
                        pattern[s] = r, res
                    else:
                        # repeat pattern found. Jump to the end
                        last_row, rounds = pattern[s]
                        res += (res-rounds) * ((rows - r + 1) / (r -last_row))
                        r += (rows - r + 1) / (r - last_row) * (r - last_row)
                # Fill word
                c += (sentence[s]+1)
                s += 1
                # Last word in sentence met. Increment res if valid
                if s == len(sentence) and r <= rows:
                    s = 0
                    res += 1
            return res
    

Log in to reply
 

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