ধরুন আমাদের কাছে একটি সারি x cols স্ক্রীন রয়েছে এবং একটি বাক্য যা অ-খালি শব্দের তালিকা দ্বারা উপস্থাপিত হয়েছে, তাহলে আমাদের খুঁজে বের করতে হবে যে প্রদত্ত বাক্যটি স্ক্রিনে কতবার লাগানো যাবে। কিছু বৈশিষ্ট্য আছে -
-
একটি শব্দ দুটি লাইনে বিভক্ত হবে না।
-
বাক্যে শব্দের ক্রম পরিবর্তন করা উচিত নয়।
-
দুটি শব্দের মধ্যে একটি মাত্র ফাঁকা থাকবে৷
৷ -
বাক্যটিতে মোট শব্দ সংখ্যা 100 এর বেশি হবে না।
-
প্রতিটি শব্দের দৈর্ঘ্য 0-এর থেকে বেশি কিন্তু 10-এর কম৷
৷ -
1 ≤ সারি, cols ≤ 20,000৷
সুতরাং যদি ইনপুটটি সারি =3 এবং cols =6 এর মত হয় এবং বাক্যটি [“a”, “bcd”, “e”] হয়, তাহলে আউটপুট হবে 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র ডিপি সংজ্ঞায়িত করুন, ret সেট করুন :=0, n :=বাক্য বিন্যাসের আকার
-
যখন সারিটি 0
নয়-
start :=ret mod n, len :=-l এবং cnt :=0
-
যদি dp-এ start উপস্থিত না থাকে, তাহলে
-
যখন 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
-
-
রিটার্ন রিটার্ন/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
