Leet Code Daily 2024-05-24 - Maximum Score Words Formed by Letters

constexpr int kNumLetters = 26;

class Solution {
public:
    int num_words;
    vector<vector<int>> cnt_letters_per_word;
    vector<int> cnt_letters;
    vector<int> score_per_word;

    int dfs(int i, int score) {
        if (i >= num_words) {
            return score;
        }
        int ret = dfs(i + 1, score);
        bool can_build = true;
        for (int c = 0; c < kNumLetters; c++) {
            if (cnt_letters_per_word[i][c] > cnt_letters[c]) {
                can_build = false;
                break;
            }
        }
        if (can_build) {
            for (int c = 0; c < kNumLetters; c++) {
                cnt_letters[c] -= cnt_letters_per_word[i][c];
            }
            ret = max(ret, dfs(i + 1, score + score_per_word[i]));
            for (int c = 0; c < kNumLetters; c++) {
                cnt_letters[c] += cnt_letters_per_word[i][c];
            }
        }
        return ret;
    }

    int maxScoreWords(vector<string>& words, vector<char>& letters,
                      vector<int>& score) {
        num_words = words.size();
        cnt_letters_per_word =
            vector<vector<int>>(num_words, vector<int>(kNumLetters, 0));
        for (int i = 0; i < num_words; i++) {
            for (const auto& c : words[i]) {
                cnt_letters_per_word[i][c - 'a']++;
            }
        }
        cnt_letters = vector<int>(kNumLetters, 0);
        for (const auto& c : letters) {
            cnt_letters[c - 'a']++;
        }
        score_per_word = vector<int>(num_words, 0);
        for (int i = 0; i < num_words; i++) {
            for (const auto& c : words[i]) {
                score_per_word[i] += score[c - 'a'];
            }
        }
        return dfs(0, 0);
    }
};