Leetcode 1255. Maximum Score Words Formed by Letters

https://leetcode.com/contest/weekly-contest-162/problems/maximum-score-words-formed-by-letters/

Notes:

The question has a small size of input, so it can be solved by brute force backtracking directly. (If size is larger, memorization may be applied, since it is an optimal combination problem in nature.)

The basic idea is that:

1): we need to count the letter numbers that can be used in total;

2): then we can go back to the strings. If any string has one or more kinds of letter with more than the previous counting, we simply cannot use it. Otherwise, we can record the counting of letter of the string, which can be used later;

3): after the first and the second steps which work like a pre-processing, we just do a backtracking to find the optimal solution.


See the code below:

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> ct(26, 0);
        for(auto &a : letters) ++ct[a-'a'];
        vector<vector<int>> cts;
        for(int i=0; i<words.size(); ++i) {
            vector<int> ct1(26, 0);
            bool valid = true;
            for(auto &a : words[i]) {
                int id = a - 'a';
                ++ct1[id];
                if(ct1[id] > ct[id]) {
                    valid = false;
                    break;
                }
            }
            if(valid) cts.push_back(ct1);
            else {words.erase(words.begin() + i); --i;}
        }
        vector<int> cur(26, 0);
        return dfs(words, 0, cts, cur, ct, score);
    }

private:
    int dfs(vector<string>& ws, int id, vector<vector<int>>& cts, vector<int> cur, vector<int>& ct, vector<int>& ss) {
        if(id == ws.size()) return 0;
        int res = 0;
        for(int i=id; i<ws.size(); ++i) {
            vector<int> t(26, 0);
            bool valid = true;
            for(int j=0; j<26; ++j) {
                t[j] = cur[j] + cts[i][j];
                if(t[j] > ct[j]) {valid = false; break;}
            }
            if(valid) {
                int one = 0;//one possible solution
                for(auto &a : ws[i]) one += ss[a-'a'];
                one += dfs(ws, i+1, cts, t, ct, ss);
                res = max(res, one);
            }
        }
        return res;
    }
};