C ++中的句子屏幕拟合

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

• 一个单词不会分成两行。

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

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

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

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

• 1≤行，col≤20,000。

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

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

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

• 当行不为0时

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

• dp [start]：= cnt

• ret：= ret + cnt

• len：= 1 + len +句子[（start + cnt）mod n]

• 增加cnt 1

• 开始：= ret mod n，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