Giả sử chúng ta có màn hình rows x cols và một câu được biểu diễn bằng danh sách các từ không rỗng. Tìm số lần câu đã cho có thể vừa vặn trên màn hình. Các tính chất:
Một từ không được tách thành hai dòng.
Thứ tự từ trong câu không được thay đổi.
Chỉ có một dấu cách giữa hai từ.
Tổng số từ không vượt quá 100.
Độ dài mỗi từ > 0 và < 10.
1 ≤ rows, cols ≤ 20.000.
Ví dụ: rows = 3, cols = 6, sentence = ["a", "bcd", "e"] → đầu ra = 2.
Để giải quyết, chúng ta làm theo các bước:
Định nghĩa map dp, ret := 0, n := kích thước sentence.
Khi rows > 0:
start := ret % n, len := -1, cnt := 0.
Nếu start chưa có trong dp: khi 1 + len + sentence[(start+cnt)%n].size() ≤ cols: len = 1 + len + size; cnt++; dp[start] = cnt; ret += cnt.
Ngược lại ret += dp[start].
rows--.
Trả về ret / n.
Ví dụ (C++)
Hãy xem triển khai sau để hiểu rõ hơn:
#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));
}
Đầu vào
["a","bcd","e"] 3 6
Đầu ra
2