C ++中字母构成的最大分数词

假设我们有一个单词列表，一个字母列表和每个字符的分数。我们必须找到使用给定字母组成的任何有效单词集的最大分数。

我们可能不会在字母中使用所有字符，并且每个字母只能使用一次。字母“ a”，“ b”，“ c”，...，“ z”的得分分别由得分[0]，得分[1]，...，得分[25]给出。

因此，如果输入像单词= [“ 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]，则输出将为30，此处good和cat得分最高。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个2D数组dp

• 定义一个函数calc()，它将使用s，一个映射m，一个数组sc，

• 回答：= 0

• 对于初始化i：= 0，当i <s的大小时，更新（将i增加1），执行-

• 返回0

• x：= s [i]

• 如果m [x] <= 0，则-

• （将m [x]减1）

• ans：= ans + sc [x-'a']

• 返回ans

• 定义一个函数solve()，它将接受i，状态，成对的v数组，一个映射m，一个数组s，

• 如果i与-1相同，则-

• 返回0

• x：= .v [i]的第二个值

• 回答：= 0

• 如果状态与1相同，则-

• ans：= calc(x,m,s)

• 如果ans> 0并且状态等于1，则-

• （将m [x [j]]减1）

• 对于初始化j：= 0，当j <x的大小时，更新（将j增加1），执行-

• 返回ans +求解(i-1,0,v,m,s)和求解(i-1,1,v,m,s)的最大值

• 从主要方法中，执行以下操作-

• 回答：= 0

• 定义一张映射

• 对于初始化i：= 0，当i <l的大小时，更新（将i增加1），执行-

• （将m [l [i]]增加1）

• 定义成对的数组v

• 对于初始化i：= 0，当i <w的大小时，更新（将i增加1），执行-

• 在v的末尾插入{flag，x}

• x：= w [i]

• 标志：= calc(x,m,s)

• 如果flag不为零，则-

• 对数组v排序

  dp：=定义一个2D数组，大小为（v的大小）x 2，并用-1填充

  返回最大的solve（v，0，v，m，s的大小）和solve（v，1，v，m，s的大小）

让我们看下面的实现以更好地理解-

示例

#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));
}

输入项

{"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}

输出结果

30