C ++中的句子屏幕拟合

假设我们有一个xcols行的屏幕和一个由非空单词列表表示的句子，因此我们必须找出给定的句子可以在屏幕上显示多少次。有某些属性-

一个单词不会分成两行。

句子中的单词顺序不得更改。

两个单词之间只有一个空格。

句子中的单词总数不超过100。

每个单词的长度大于0但小于10。

1≤行，col≤20,000。

因此，如果输入类似于rows=3并且cols=6，并且句子为[“a”，“bcd”，“e”]，则输出为2。

为了解决这个问题，我们将遵循以下步骤-

定义映射dp，设置ret：=0，n：=句子数组的大小

当行不为0时

而1+len+句子的大小[（start+cnt）modn]<=cols

dp[start]：=cnt

ret：=ret+cnt

len：=1+len+句子[（start+cnt）modn]

增加cnt1

开始：=retmodn，len：=-l和cnt：=0

如果dp中不存在start，则

否则ret：=ret+dp[start]

行：=行–1

返回ret/n

范例（C++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h> using namespace std; class Solution { public: int wordsTyping(vector<string>& sentence, int rows, int cols) { unordered_map <int, int> dp; int ret = 0; int n = sentence.size(); while(rows--){ int start = ret % n; int len = -1; int cnt = 0; if(!dp.count(start)){ while(1 + len + (int)sentence[(start + cnt) % n].size() <= cols){ len = 1 + len + sentence[(start + cnt) % n].size(); cnt++; } dp[start] = cnt; ret += cnt; } else{ ret += dp[start]; } } return ret / n; } }; main(){ vector<string> v = {"a","bcd","e"}; Solution ob; cout << (ob.wordsTyping(v, 3, 6)); }

输入项

["a","bcd","e"] 3 6

输出结果

2