Các từ có điểm tối đa được tạo thành bởi các chữ cái trong C ++

Giả sử chúng ta có một danh sách các từ, một danh sách các chữ cái đơn lẻ và điểm cho mọi ký tự. Chúng ta phải tìm điểm tối đa của bất kỳ tập hợp từ hợp lệ nào được tạo thành bằng cách sử dụng các chữ cái đã cho.

Chúng tôi không thể sử dụng tất cả các ký tự trong các chữ cái và mỗi chữ cái chỉ có thể được sử dụng một lần. Điểm của các chữ cái 'a', 'b', 'c', ..., 'z' lần lượt là điểm [0], điểm [1], ..., điểm [25].

Vì vậy, nếu đầu vào là các từ =["god", "good", "toc", "cat"], chữ cái =[a, g, o, o, d, d, d, c, t, t] và điểm =[5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0, 0,0,0], thì đầu ra sẽ là 30, ở đây là tốt và con mèo đang đạt điểm tối đa.

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

Xác định một dp mảng 2D
Xác định một hàm calc (), hàm này sẽ lấy s, một ánh xạ m, một mảng sc,
ans:=0
để khởi tạo i:=0, khi i
- x:=s [i]
- nếu m [x] <=0, thì -
  - trả về 0
- (giảm m [x] đi 1)
- ans:=ans + sc [x - 'a']
trả lại ans
Xác định một hàm giải quyết (), điều này sẽ lấy i, trạng thái, một mảng các cặp v, một ánh xạ m, một mảng s,
nếu tôi giống -1, thì -
- trả về 0
x:=.giá trị thứ hai của v [i]
ans:=0
nếu trạng thái giống như 1, thì -
- ans:=calc (x, m, s)
nếu ans> 0 và trạng thái giống như 1, thì -
- để khởi tạo j:=0, khi j
  - (giảm m [x [j]] đi 1)
trả về ans + tối đa của giải (i - 1, 0, v, m, s) và giải (i - 1, 1, v, m, s)
Từ phương thức chính, thực hiện như sau -
ans:=0
Xác định một bản đồ m
để khởi tạo i:=0, khi i
- (tăng m [l [i]] lên 1)
Xác định một mảng v gồm các cặp
để khởi tạo i:=0, khi i
- x:=w [i]
- cờ:=calc (x, m, s)
- nếu cờ khác 0, thì -
  - chèn {flag, x} vào cuối v
sắp xếp mảng v

dp:=Xác định một mảng 2D có kích thước (kích thước v) x 2 và điền vào giá trị này bằng -1

trả về tối đa của giải (kích thước của v, 0, v, m, s) và giải quyết (kích thước của v, 1, v, m, s)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<vector<int> > dp;
   int calc(string s, map<char, int> m, vector<int>& sc){
      int ans = 0;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (m[x] <= 0)
            return 0;
         m[x]--;
         ans += sc[x - 'a'];
      }
      return ans;
   }
   int solve(int i, int status, vector<pair<int, string> > v,
   map<char, int> m, vector<int>& s){
      if (i == -1)
         return 0;
      string x = v[i].second;
      int ans = 0;
      if (status == 1)
         ans = calc(x, m, s);
      if (ans > 0 && status == 1) {
         for (int j = 0; j < x.size(); j++) {
            m[x[j]]--;
         }
      }
      return ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s));
   }
   int maxScoreWords(vector<string>& w, vector<char>& l,
   vector<int>& s){
      int ans = 0;
      map<char, int> m;
      for (int i = 0; i < l.size(); i++)
         m[l[i]]++;
      vector<pair<int, string> > v;
      for (int i = 0; i < w.size(); i++) {
         string x = w[i];
         int flag = calc(x, m, s);
         if (flag) {
            v.push_back({ flag, x });
         }
      }
      sort(v.begin(), v.end());
      dp = vector<vector<int> >(v.size(), vector<int>(2, -1));
      return max(solve(v.size() - 1, 0, v, m, s), solve(v.size() -
      1, 1, v, m, s));
   }
};
main(){
   Solution ob;
   vector<string> words = {"god", "good", "toc", "cat"};
   vector<char> letters = {'a','g','o','o','d','d','d','c','t','t'};
   vector<int> score = {5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0};
   cout << (ob.maxScoreWords(words, letters, score));
}

Đầu vào

{"god", "good", "toc", "cat"},
{'a','g','o','o','d','d','d','c','t','t'},
{5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0}

Các từ có điểm tối đa được tạo thành bởi các chữ cái trong C ++

Ví dụ

Đầu vào

Đầu ra