难度: Medium
Submission
运行时间: 95 ms
内存: 16.0 MB
class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
s = ""
for word in sentence:
if len(word) > cols:
return 0
s += word + " "
validSpace = 0
n = len(s)
for _ in range(rows):
validSpace += cols
while s[validSpace % n] != " ":
validSpace -= 1
validSpace += 1
return validSpace // n
Explain
这个题解的思路是先把句子数组拼接成一个长字符串，每个单词之间用空格隔开。然后模拟在屏幕上填充这个长字符串，同时记录填充的有效空格数。最后用有效空格数除以长字符串的长度，就可以得到句子在屏幕上重复的次数。在模拟填充的过程中，如果当前行放不下下一个单词，就需要把当前行剩余的空格略过，把下一个单词放到下一行。
时间复杂度: O(max(mw, rows * cols))
空间复杂度: O(mw)
class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
# 将句子数组拼接成一个长字符串
s = ""
for word in sentence:
if len(word) > cols:
return 0
s += word + " "
validSpace = 0
n = len(s)
# 模拟在屏幕上填充长字符串
for _ in range(rows):
validSpace += cols
# 如果当前行放不下下一个单词，就略过剩余空格
while s[validSpace % n] != " ":
validSpace -= 1
validSpace += 1
# 有效空格数除以字符串长度，得到重复次数
return validSpace // n
Explore
这个逻辑是基于屏幕无法显示整个单词的现实限制。如果句子中的任何一个单词长度超过了屏幕的列数，那么该单词无法在屏幕上完整显示，也就不可能在任何行中完整地显示这个单词。因此，整个句子也无法在屏幕上循环显示，所以直接返回0是为了避免进一步无效的计算。
在拼接句子时每个单词后添加一个空格是为了模拟句子在屏幕上的实际显示方式，其中单词之间通常需要有空格分隔。这样做可以确保在计算每行可以容纳的单词数时能够准确地处理单词间的间隔。这对算法的逻辑有关键影响，因为它使得整个句子可以作为一个连续的循环字符串来处理，而且在模拟填充过程中可以更简单地判断何时一个单词结束并转向下一个单词。
使用有效空格数除以整个字符串长度来计算重复次数是基于整个字符串（包括单词和它们之间的空格）被视为一个循环单位的原理。每次整个字符串长度的有效空格被填满，意味着句子重复了一次。这种方法的准确性由算法设计保证，确保每轮循环结束时，都恰好完成了一个或多个完整的字符串的循环，精确地计算了句子在给定行和列限制下可以重复的次数。
这个操作是为了解决当当前行剩余的空间不足以容纳下一个单词时的问题。如果在当前行填充时达到或超过行的界限，而在那一点上的字符不是空格（意味着它是单词的一部分），则需要回退到最后一个空格字符。这样做可以确保不会将一个单词拆分到两行显示，避免了单词的断裂显示。通过这种方式，算法确保每行都只显示完整的单词，维持了显示的整洁和正确性。