1255. Maximum Score Words Formed by Letters

Given a list of words, list of single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters ‘a’, ‘b’, ‘c’, … ,’z’ is given by score[0], score[1], … , score[25] respectively.

class Solution {
    set<int> checked;
    int combination(int choose, vector<int> used, vector<int>& letter, unordered_map<int, pair<int, vector<int>>>& pair, int maxLen) {
        if(checked.count(choose)) return 0;
        checked.insert(choose);
        int ret = 0;
        for(int i = 0; i < maxLen; i++) {
            if(choose & (1<<i) || !pair.count(i)) continue;
            int nextChoose = choose ^ (1<<i);
            vector<int> nextUsed(used.begin(), used.end());
            bool canNext = true;
            for(int j = 0; j < 26; j++) {
                nextUsed[j] += pair[i].second[j];
                if(nextUsed[j] > letter[j]) {
                    canNext = false;
                    break;
                }
            }
            if(canNext) {
                ret = max(ret, combination(nextChoose, nextUsed, letter, pair, maxLen) + pair[i].first);
            }
        }
        return ret;
    }
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> letter(26, 0);
        unordered_map<int, pair<int, vector<int>>> m;
        for(auto& c : letters) { letter[c - 'a']++; }
        for(int i = 0; i < words.size(); i++) {
            vector<int> cmp(26, 0);
            bool flag = true;
            int cur(0);
            for(auto& c : words[i]) {
                if(++cmp[c - 'a'] > letter[c - 'a']) {
                    flag = false;
                    break;
                }
                cur += score[c - 'a'];
            }
            if(flag) {
                m[i] = {cur, cmp};
            }
        }


        return combination(0, vector<int>(26, 0), letter, m, words.size());
    }
};

class Solution {
    int check(vector<string>& words, vector<int>& letter, vector<int>& sc, int idx) {
        if(idx >= words.size()) return 0;
        int res1 = check(words, letter, sc, idx + 1), score = 0, possible = 1;
        vector<int> cur(begin(letter), end(letter));
        for(auto& c : words[idx]) {
            if(--cur[c - 'a'] < 0) {
                possible = 0;
                break;
            }
            score += sc[c - 'a'];
        }
        return max(res1, possible ? score + check(words, cur, sc, idx + 1) : 0);
    }
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> letter(26, 0);
        for(auto& c : letters) { letter[c - 'a']++; }
        return check(words, letter, score, 0);
    }
};