Python solution with detailed explanation


  • 1
    G

    Solution

    Sentence Screen Fitting https://leetcode.com/problems/sentence-screen-fitting/

    Caching Solution - TLE

    • The first approach is to fit word by word of the sentence. build_sentence takes a starting column id and fills out the entire sentence. It returns the next_col_id and the row offset required to fill the sentence.
    • Now once we get the new row offset, we test if the additional sentence will fit in our matrix or not - i.e. do we have sufficient rows to fill it or not?
    • In addition, we cache the offset and new col_id, so that the next time the pattern repeats, we dont need to recompute.
    class Solution1(object):
        def build_sentence(self, sentence, col_id, cols):
            row, i = 0, 0
            while i < len(sentence):
                x = len(sentence[i])
                if x + col_id <= cols:
                    i += 1
                    col_id += x
                    (col_id, row) = (0, row + 1) if col_id == cols or col_id + 1 == cols else (col_id + 1, row)
                else:
                    col_id, row = 0, row+1
            return (col_id, row)
     
        def wordsTyping(self, sentence, rows, cols):
            """
            :type sentence: List[str]
            :type rows: int
            :type cols: int
            :rtype: int
            """
            if any(map(lambda x: len(x) > cols, sentence)):
                return 0
            row_id, col_id = 0, 0
            i, sc = 0, 0
            cache = {}
            while True:
                if col_id not in cache:
                    cache[col_id] = self.build_sentence(sentence, col_id, cols)
                (col_id, offset) = cache[col_id]
                row_id += offset
                if row_id < rows:
                    sc += 1
                elif row_id == rows and col_id == 0:
                    sc += 1
                    break
                else:
                    break
            return sc
    

    Optimized Solution

    • Iterate over every possible row
    • Try to fill the row's columns with as many sentence characters as possible.
    • Test the next character in sentence after filling cols character. Use modulo operator for this.
    • If this is an " " string, then we are good. Otherwise move back till we get a " ".
    • Now increment valid_ch_count by 1 to account for this " "
    • Run the code for corner cases: s = "abc de " and col = 7. valid_ch_cnt = (0+7) = 7. This points to 7%7 or s[0]. So we move back 1 and valid_ch_cnt becomes 6 and will point to last character which is " ". Then we increment to include this charcater.
    • Similarly run a case for s = "abc de " and row=2 and col = 6. Notice that "abc de" aligns with the column boundary. But the valid_ch_count is still 7 after first row. In the second row, we have valid_ch_count as 7 + 6 = 13. Finally it turns out to be 14 and 14/7 = 2. Notice we do not take a modulo with cols, but with len(s) and hence get the right answer.
    • This artimetic makes sure that valid_ch_count // len(s) gives the right answer.
    class Solution(object):
        def wordsTyping(self, sentence, rows, cols):
            """
            :type sentence: List[str]
            :type rows: int
            :type cols: int
            :rtype: int
            """
            s, valid_ch_cnt = " ".join(sentence) + " ", 0
            for i in range(rows):
                valid_ch_cnt += cols
                while s[valid_ch_cnt%len(s)] != " ":
                    valid_ch_cnt -= 1
                valid_ch_cnt += 1 # Add the empty space to count of valid characters
            return valid_ch_cnt // len(s)
    

Log in to reply
 

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