[LeetCode]Sentence Screen Fitting

题目描述:

LeetCode 418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of words, find how many times the given sentence can be fitted on the screen.

Note:

  1. A word cannot be split into two lines.
  2. The order of words in the sentence must remain unchanged.
  3. Two consecutive words in a line must be separated by a single space.
  4. Total words in the sentence won't exceed 100.
  5. Length of each word won't exceed 10.
  6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

题目大意:

给定一个rows x cols屏幕与一列单词表示的句子,计算屏幕中可以展示多少次完整的句子。

注意:

  1. 单词不能拆成两行
  2. 单词在句子中的顺序不能调换
  3. 两个相邻单词之间必须有一个空格隔开
  4. 句子的总单词数不超过100
  5. 每个单词的长度不超过10
  6. 1 ≤ rows, cols ≤ 20,000.

解题思路:

由于rows和cols的规模可以达到20000,因此朴素的解法会超时(Time Limit Exceeded)

观察测试用例3可以发现,当句子在屏幕上重复展现时,会呈现周期性的规律:

I-had
apple
pie-I
had--
apple
pie-I
had--
apple

上例中apple单词的相对位置从第二行开始循环,因此只需要找到单词相对位置的“循环节”,即可将问题简化。

利用字典dp记录循环节的起始位置,具体记录方式为:dp[(pc, pw)] = pr, ans

以数对(pc, pw)为键,其中pw为单词在句子中出现时的下标,pc为单词出现在屏幕上的列数

以数对(pr, ans)为值,其中pr为单词出现在屏幕上的行数,ans为此时已经出现过的完整句子数

Python代码:

class Solution(object):
    def wordsTyping(self, sentence, rows, cols):
        """
        :type sentence: List[str]
        :type rows: int
        :type cols: int
        :rtype: int
        """
        wcount = len(sentence)
        wlens = map(len, sentence)
        slen = sum(wlens) + wcount
        dp = dict()
        pr = pc = pw = ans = 0
        while pr < rows:
            if (pc, pw) in dp:
                pr0, ans0 = dp[(pc, pw)]
                loop = (rows - pr0) / (pr - pr0 + 1)
                ans = ans0 + loop * (ans - ans0)
                pr = pr0 + loop * (pr - pr0)
            else:
                dp[(pc, pw)] = pr, ans
            scount = (cols - pc) / slen
            ans += scount
            pc += scount * slen + wlens[pw]
            if pc <= cols:
                pw += 1
                pc += 1
                if pw == wcount:
                    pw = 0
                    ans += 1
            if pc >= cols:
                pc = 0
                pr += 1
        return ans

 

本文链接:http://bookshadow.com/weblog/2016/10/09/leetcode-sentence-screen-fitting/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码