C++-এ অক্ষর দিয়ে শব্দ বানিয়ে সর্বোচ্চ স্কোর (Maximum Score Words Formed by Letters)

একটি শব্দের তালিকা, একক অক্ষরগুলির তালিকা এবং প্রতিটি অক্ষরের স্কোর দেওয়া আছে। দেওয়া অক্ষরগুলো ব্যবহার করে যেকোনো বৈধ শব্দ সেট বানিয়ে সর্বোচ্চ স্কোর বের করতে হবে। প্রতিটি অক্ষর শুধু একবার ব্যবহার করা যায়।

উদাহরণ

ইনপুট:

words = ["god", "good", "toc", "cat"]
letters = [a,g,o,o,d,d,d,c,t,t]
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]

আউটপুট: 30 (good এবং cat শব্দ দুটি সর্বোচ্চ স্কোর তৈরি করে)

সমাধানের ধাপসমূহ

প্রতিটি শব্দের জন্য তা বানানো সম্ভব কিনা এবং এর স্কোর কত তা চেক করুন।
ব্যাকট্র্যাকিং (backtracking) বা DP ব্যবহার করে সব সম্ভাব্য শব্দ কবিনেশন চেষ্টা করুন।
মেমোইজেশন (memoization) ব্যবহার করে ওভারল্যাপিং সাবপ্রব্লেম এড়িয়ে চলুন।
সর্বোচ্চ স্কোর রিটার্ন করুন।

প্রোগ্রাম উদাহরণ

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

int 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}