Khớp màn hình câu trong C ++

Giả sử chúng ta có màn hình row x cols và một câu được biểu thị bằng danh sách các từ không trống, vì vậy chúng ta phải tìm xem câu đã cho có thể được lắp trên màn hình bao nhiêu lần. Có một số thuộc tính nhất định -

Một từ sẽ không được chia thành hai dòng.
Thứ tự các từ trong câu không được thay đổi.
Sẽ chỉ có một khoảng trắng giữa hai từ.
Tổng số từ trong câu sẽ không vượt quá 100.
Độ dài của mỗi từ lớn hơn 0 nhưng nhỏ hơn 10.
1 ≤ hàng, cols ≤ 20.000.

Vì vậy, nếu đầu vào giống như row =3 và cols =6 và câu là [“a”, “bcd”, “e”], thì đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định bản đồ dp, đặt ret:=0, n:=kích thước của mảng câu
trong khi hàng không phải là 0
- start:=ret mod n, len:=-l và cnt:=0
- nếu start không có trong dp thì
  - while 1 + len + kích thước của câu [(start + cnt) mod n] <=cols
    - len:=1 + len + câu [(start + cnt) mod n]
    - tăng cnt lên 1
  - dp [start]:=cnt
  - ret:=ret + cnt
- nếu không thì ret:=ret + dp [start]
- row:=row - 1
trả về ret / n

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách 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;
   }
};
main(){
   vector<string> v = {"a","bcd","e"};
   Solution ob;
   cout << (ob.wordsTyping(v, 3, 6));
}

Đầu vào

["a","bcd","e"]
3
6

Khớp màn hình câu trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra