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]

आउटपुट

व्याख्या: "good" और "cat" अधिकतम स्कोर 30 देते हैं।

समाधान दृष्टिकोण (बैकट्रैकिंग + मेमोइजेशन)

उपलब्ध अक्षरों की गिनती मैप में संग्रहीत करें।
प्रत्येक शब्द के लिए, जांचें कि क्या वर्तमान अक्षरों से बनाया जा सकता है और उसका स्कोर गणना करें।
केवल वैध शब्दों को रखें।
पुनरावर्ती रूप से प्रत्येक शब्द को शामिल करने या न करने का प्रयास करें (बैकट्रैकिंग)।
मेमोइजेशन (DP) का उपयोग करके दोहराव से बचें।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> dp;
    
    int calcScore(string& s, map<char, int>& avail, vector<int>& sc) {
        int ans = 0;
        for (char c : s) {
            if (avail[c] <= 0) return 0;
            avail[c]--;
            ans += sc[c - 'a'];
        }
        return ans;
    }
    
    int solve(int i, int take, vector<pair<int, string>>& words, 
              map<char, int> avail, vector<int>& sc) {
        if (i == -1) return 0;
        
        string word = words[i].second;
        int ans = 0;
        if (take) {
            ans = calcScore(word, avail, sc);
        }
        if (ans > 0 && take) {
            for (char c : word) avail[c]--;
        }
        return ans + max(solve(i-1, 0, words, avail, sc), 
                         solve(i-1, 1, words, avail, sc));
    }
    
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        map<char, int> avail;
        for (char c : letters) avail[c]++;
        
        vector<pair<int, string>> validWords;
        for (string& w : words) {
            map<char, int> temp = avail;
            int sc = calcScore(w, temp, score);
            if (sc > 0) validWords.push_back({sc, w});
        }
        
        sort(validWords.begin(), validWords.end());
        dp = vector<vector<int>>(validWords.size(), vector<int>(2, -1));
        
        return max(solve(validWords.size()-1, 0, validWords, avail, score),
                   solve(validWords.size()-1, 1, validWords, avail, score));
    }
};

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);
    return 0;
}