C++でのセンテンススクリーンフィッティング

行x列の画面と、空でない単語のリストで表される文があるとします。したがって、指定された文を画面に何回収めることができるかを見つける必要があります。特定のプロパティがあります-

• 単語は2行に分割されません。

• 文中の語順は変更しないでください。

• 2つの単語の間にスペースは1つだけあります。

• 文中の単語の総数は100を超えません。

• 各単語の長さは0より長く10未満です。

• 1≤行、列≤20,000。

したがって、入力がrows=3およびcols=6のようで、文が[“ a”、“ bcd”、“ e”]の場合、出力は2になります。

これを解決するには、次の手順に従います-

• マップdpを定義し、ret：=0、n：=文の配列のサイズを設定します

• 行が0ではない間

  • start：=ret mod n、len：=-lおよびcnt：=0

  • startがdpに存在しない場合、

    • 一方、1 + len +文のサイズ[（start + cnt）mod n] <=cols

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

      • cntを1増やします

    • dp [start]：=cnt

    • ret：=ret + cnt

  • それ以外の場合、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