मान लीजिए हमारे पास rows x cols स्क्रीन है और एक सेंटेंस जिसे नॉन-एम्प्टी वर्ड्स की लिस्ट द्वारा दर्शाया गया है, तो हमें यह पता लगाना है कि दी गई सेंटेंस को स्क्रीन पर कितनी बार फिट किया जा सकता है। कुछ प्रॉपर्टीज़ हैं:
एक वर्ड को दो लाइन्स में स्प्लिट नहीं किया जाएगा।
सेंटेंस में वर्ड्स का क्रम नहीं बदला जाना चाहिए।
दो वर्ड्स के बीच केवल एक स्पेस होगा।
सेंटेंस में वर्ड्स की कुल संख्या 100 से अधिक नहीं होगी।
प्रत्येक वर्ड की लंबाई 0 से अधिक लेकिन 10 से कम है।
1 ≤ rows, cols ≤ 20,000।
उदाहरण के लिए, अगर इनपुट है rows = 3 और cols = 6, और सेंटेंस है ["a", "bcd", "e"], तो आउटपुट 2 होगा।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
एक मैप dp डिफाइन करें, ret := 0 सेट करें, n := सेंटेंस ऐरे का साइज
जब तक row 0 नहीं है:
start := ret mod n, len := -1 और cnt := 0
अगर start dp में मौजूद नहीं है, तो:
जब तक 1 + len + साइज of sentence[(start + cnt) mod n] <= cols:
len := 1 + len + sentence[(start + cnt) mod n].size()
cnt को 1 से बढ़ाएं
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;
}
};
int main(){
vector<string> v = {"a","bcd","e"};
Solution ob;
cout << (ob.wordsTyping(v, 3, 6));
}
इनपुट
["a","bcd","e"] 3 6
आउटपुट
2