## 题目描述：

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:
apple
pie-I

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

## 题目大意：

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

## 解题思路：

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

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

## 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
``````

Pingbacks已关闭。

1. 张皆浩 发布于 2016年10月14日 10:33 #

为什么是(pr - pr0 + 1)

2. 在线疯狂 发布于 2016年10月14日 16:24 #

pr - pr0 + 1计算上一次出现时的行数pr0，与当前行pr之间一共包含多少行，包含边界