ধরুন আমাদের একটি rows x cols স্ক্রিন আছে এবং একটি সেন্টেন্স যা নন-এম্পটি শব্দের একটি লিস্ট দিয়ে রিপ্রেজেন্ট করা হয়েছে। আমাদের বের করতে হবে দেওয়া সেন্টেন্সটি কতবার স্ক্রিনে ফিট করা যায়। কিছু বৈশিষ্ট্য:
এক শব্দ দুটি লাইনে ভাগ হবে না।
সেন্টেন্সের শব্দের অর্ডার পরিবর্তন করা যাবে না।
দুই শব্দের মাঝপথে শুধু এক স্পেস থাকবে।
সেন্টেন্সে মোট শব্দের সংখ্যা ১০০-এক্সিড করবে না।
প্রতিটি শব্দের দৈর্ঘ্য ০-এর চেয়ে বড় কিন্তু ১০-এর চেয়ে ছোট।
১ ≤ rows, cols ≤ ২০,০০০।
উদাহরণস্বরূপ, rows = 3, cols = 6, এবং সেন্টেন্স [“a”, “bcd”, “e”] হলে আউটপুট হবে ২।
সমাধানের ধাপগুলো:
একটি map dp ডিফাইন করুন, ret := 0, n := sentence array-এর সাইজ
যখন row 0 নয়
start := ret mod n, len := -1 এবং cnt := 0
যদি start dp-এ না থাকে, তবে
যখন 1 + len + sentence[(start + cnt) mod n]-এর সাইজ <= cols
len := 1 + len + sentence[(start + cnt) mod n]-এর সাইজ
cnt ১ বাড়ান
dp[start] := cnt
ret := ret + cnt
অন্যথায় ret := ret + dp[start]
row := row – 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
