Can someone help me speed up my solution, I feel this should be fast enough


  • 0
    I

    My solution essentially relies on the following optimization.
    Say we have sentence = ["a","b","c"], and cols = 3, rows = 11

    now the screen will look something like:

    a b
    c a
    b c
    a b <-- repeating pattern here
    c a
    b c
    a b <--- repeating pattern again here
    c a
    b c
    a b <-- another repeating pattern starts here but doesn't finish
    c a

    So basically I figure out how many rows are taken up by one "repeating pattern" (call this repeat_pat_rows in code) and how many sentences you can fit inside one repeating pattern (call this repeat_pat_sentence_cnt in code). Then if i divide rows by repeat_pat_rows, I get the total number of whole repeating patterns (called repeat_pat_cnt in code). Then multiply repeat_pat_cnt * repeat_pat_sentence_cnt tells me how many sentences can fit in all of the repeating patterns.

    Now, of course there may be some rows near the end of the screen that is not quite a repeating pattern, as show in my example above. The remainder of the division of rows with repeat_pat_rows tells me how many such rows there are (called remain_rows in code).
    Then, I just manually count how many sentences can fit in this remaining portion using my calc_sentence_cnt method again (which should be fairly small), and add it to the number of sentences that could fit in the repeating patterns. This is honestly the only optimization I can think of ... :( Would this be acceptable in interview? IT passes 32/51 cases but fails on this case:
    ["a","bcd"]
    20000
    20000

    class Solution(object):
        def calc_sentence_cnt(self, sentence, rows, cols, repeated_pattern_counting):
            word_idx = 0
            space_rem = cols
            row = 1
            sentence_fit_cnt = 0
            
            while row <= rows:
                if len(sentence[word_idx]) <= space_rem:
                    if len(sentence[word_idx]) == space_rem:
                        space_rem -= len(sentence[word_idx])
                    else:
                        space_rem -= (len(sentence[word_idx]) + 1)
                        
                    if word_idx == len(sentence) - 1:
                        sentence_fit_cnt += 1
                        
                    word_idx = (word_idx + 1) % len(sentence)
                        
                else:
                    if repeated_pattern_counting and word_idx == 0:
                        break 
                    
                    row += 1
                    space_rem = cols
                        
            return row, sentence_fit_cnt
        
        def wordsTyping(self, sentence, rows, cols):
            """
            :type sentence: List[str]
            :type rows: int
            :type cols: int
            :rtype: int
            """
            if not sentence:
                return 0
                
            repeat_pat_rows, repeat_pat_sentence_cnt = self.calc_sentence_cnt(sentence, rows, cols, True) 
            repeat_pat_cnt, remain_rows = divmod(rows, repeat_pat_rows)
            sentence_fit_cnt = repeat_pat_cnt * repeat_pat_sentence_cnt
            
            sentence_fit_cnt += self.calc_sentence_cnt(sentence, remain_rows, cols, False)[1]
            return sentence_fit_cnt

Log in to reply
 

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