सी++ में सेंटेंस स्क्रीन फिटिंग

मान लीजिए कि हमारे पास एक पंक्ति x cols स्क्रीन है और एक वाक्य गैर-रिक्त शब्दों की सूची द्वारा दर्शाया गया है, इसलिए हमें यह पता लगाना होगा कि दिए गए वाक्य को स्क्रीन पर कितनी बार फिट किया जा सकता है। कुछ गुण हैं -

• एक शब्द दो पंक्तियों में विभाजित नहीं होगा।

• वाक्य में शब्दों का क्रम नहीं बदला जाना चाहिए।

• दो शब्दों के बीच केवल एक स्थान होगा।

• वाक्य में शब्दों की कुल संख्या 100 से अधिक नहीं होगी।

• प्रत्येक शब्द की लंबाई 0 से अधिक लेकिन 10 से कम है।

• 1 पंक्तियाँ, कॉलम 20,000।

तो अगर इनपुट पंक्तियों =3 और कॉल्स =6 की तरह है, और वाक्य ["ए", "बीसीडी", "ई"] है, तो आउटपुट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• नक्शा डीपी परिभाषित करें, रिट सेट करें:=0, एन:=वाक्य सरणी का आकार

• जबकि पंक्ति 0 नहीं है

  • प्रारंभ:=रिट मॉड एन, लेन:=-एल और सीएनटी:=0

  • यदि प्रारंभ dp में मौजूद नहीं है, तो

    • जबकि 1 + लेन + वाक्य का आकार [(प्रारंभ + cnt) mod n] <=cols

      • लेन:=1 + लेन + वाक्य [(प्रारंभ + cnt) मॉड n]

      • cnt को 1 से बढ़ाएँ

    • डीपी [शुरू]:=सीएनटी

    • रिट:=रिट + सीएनटी

  • अन्यथा रिट:=रिट + डीपी [शुरू]

  • पंक्ति :=पंक्ति – 1

• रिटर्न रिट/एन

उदाहरण (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