题目

给你一个 rows x cols 的屏幕和一个用 非空 的单词列表组成的句子，请你计算出给定句子可以在屏幕上完整显示的次数。

注意：

  • 一个单词不能拆分成两行。
  • 单词在句子中的顺序必须保持不变。
  • 在一行中 的两个连续单词必须用一个空格符分隔。
  • 句子中的单词总量不会超过 100。
  • 每个单词的长度大于 0 且不会超过 10。
  • 1 ≤ rows, cols ≤ 20,000.

示例 1：

  1. 输入：
  2. rows = 2, cols = 8, 句子 sentence = ["hello", "world"]
  4. 输出： 1
  6. 解释：
  7. hello---
  8. world---
  10. 字符 '-' 表示屏幕上的一个空白位置。

示例 2：

  1. 输入：
  2. rows = 3, cols = 6, 句子 sentence = ["a", "bcd", "e"]
  4. 输出： 2
  6. 解释：
  7. a-bcd- 
  8. e-a---
  9. bcd-e-
  11. 字符 '-' 表示屏幕上的一个空白位置。

示例 3：

输入：
rows = 4, cols = 5, 句子 sentence = ["I", "had", "apple", "pie"]

输出： 1

解释：
I-had
apple
pie-I
had--

字符 '-' 表示屏幕上的一个空白位置。

方案一（动态规划）

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        '''
        贪心策略，每一行需要能放下最多的单词
        问题分解：
            当前行放置的词+后续行放置的词
        '''
        dp = [0]  # dp[row] 表示第row行能放置的句子的数目
        take_space_col = len('-'.join(sentence)) + 1 # 一个 sentence 能占用一行的宽度

        count = 0  # 表示放置已放置词的数量, count % len(sentence) == 带放置词的索引
        for row in range(1, rows + 1):
            index = count % len(sentence)
            # 单词的长度大于行的宽度
            if len(sentence[index]) > cols:
                return 0
            # 当前行剩余的空间大于等于带放置的下一个词的长度
            # remain = cols
            # cur = 0  # 当前行放置的 sentence 的数量
            # 根据一个 sentence 能占用一行的最大宽度首先计算出这一行能放置句子的数目
            cur, remain = divmod(cols, take_space_col)
            while remain >= len(sentence[index]):
                remain -= len(sentence[index])
                remain -= 1
                count += 1
                # 放置词到下一个循环
                index = count % len(sentence)
                if index == 0:
                    cur += 1
            # 计算当前 dp
            dp.append(dp[row - 1] + cur)
            # 如果这一行的结尾正好是 sentence 的开头，则表示前 row 行正好放置了 dp[row] 个 sentence
            # 此时可以直接退出循环，根据剩余行数计算出答案
            if index == 0:
                break

        if row != rows:
            # return int(dp[row] / row * rows)  # 把乘法放前面，不然有的测试会因为精度问题而出错
            return int(dp[row] * rows / row)  # 平均每行放置的个数 * 总行数

        return dp[-1]

优化空间复杂度

class Solution:
    def wordsTyping(self, sentence: [str], rows: int, cols: int) -> int:
        '''
        贪心策略，每一行需要能放下最多的单词
        问题分解：
            当前行放置的词+后续行放置的词
        '''
        dp_pre, dp_curr = 0, 0
        take_space_col = len('-'.join(sentence)) + 1 # 一个 sentence 能占用一行的宽度

        count = 0  # 表示放置已放置词的数量, count % len(sentence) == 带放置词的索引
        for row in range(1, rows + 1):
            index = count % len(sentence)
            # 单词的长度大于行的宽度
            if len(sentence[index]) > cols:
                return 0
            # 当前行剩余的空间大于等于带放置的下一个词的长度
            # remain = cols
            # cur = 0  # 当前行放置的 sentence 的数量
            # 根据一个 sentence 能占用一行的最大宽度首先计算出这一行能放置句子的数目
            cur, remain = divmod(cols, take_space_col)
            while remain >= len(sentence[index]):
                remain -= len(sentence[index])
                remain -= 1
                count += 1
                # 放置词到下一个循环
                index = count % len(sentence)
                if index == 0:
                    cur += 1
            # 计算当前 dp
            dp_curr = dp_pre + cur
            dp_pre = dp_curr
            # 如果这一行的结尾正好是 sentence 的开头，则表示前 row 行正好放置了 dp[row] 个 sentence
            # 此时可以直接退出循环，根据剩余行数计算出答案
            if index == 0:
                break

        if row != rows:
            # return int(dp[row] / row * rows)  # 把乘法放前面，不然有的测试会因为精度问题而出错
            return int(dp_curr * rows / row)  # 平均每行放置的个数 * 总行数

        return dp_curr

方案二（leetcode性能最高的答案）

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        whole = " ".join(sentence)
        whole += " "
        totalNum = 0
        for i in range(rows):
            totalNum += cols
            if whole[totalNum % len(whole)] == " ":
                totalNum += 1
            else:
                while whole[(totalNum - 1) % len(whole)] != " ":
                    totalNum -= 1
        return totalNum // len(whole)
  • 没看懂！！！
  • totalNum 应是每一行利用的空间

https://leetcode-cn.com/problems/sentence-screen-fitting/solution/wordjia-kong-ge-zu-cheng-stringlei-si-yu-tan-xin-s/

原文

https://leetcode-cn.com/explore/interview/card/google-interview/76/dynamic-programming/259/