Sponsored
Sponsored
This approach uses backtracking to explore all possible subsets of the list of words. For each possible subset, we calculate the score by adding scores of words whose characters can be covered by the given letters. The final solution is the maximum score achievable from all possible combinations.
Time Complexity: O(2^n), where n is the number of words. This is because we're considering every possible subset of the set of words.
Space Complexity: O(n), where n is the depth of the recursion stack.
1var maxScoreWords = function(words, letters, score) {
2 let freq = Array(26).fill(0);
3 for (let letter of letters) {
4 freq[letter.charCodeAt(0) - 'a'.charCodeAt(0)]++;
5 }
6
7 const backtrack = (index) => {
8 if (index === words.length) return 0;
9
10 let skip = backtrack(index + 1);
11
12 let wordScore = 0;
13 let canForm = true;
14 let wordFreq = Array(26).fill(0);
15 for (let char of words[index]) {
16 wordFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
17 if (wordFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)] > freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]) {
18 canForm = false;
19 break;
20 }
21 wordScore += score[char.charCodeAt(0) - 'a'.charCodeAt(0)];
22 }
23
24 let use = 0;
25 if (canForm) {
26 for (let char of words[index]) {
27 freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
28 }
29 use = wordScore + backtrack(index + 1);
30 for (let char of words[index]) {
31 freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
32 }
33 }
34
35 return Math.max(skip, use);
36 }
37
38 return backtrack(0);
39};The JavaScript implementation makes use of a frequency array to keep track of available letters. The backtrack function is recursively called to calculate possible maximum scores by skipping or using each word in turn.
In this approach, we use dynamic programming to calculate the maximum score. A common dynamic programming technique involves using a bitmask to represent the set of words included in the current set, allowing us to avoid recalculating results for previously solved subproblems.
Time Complexity: O(n * 2^n), where n is the number of words.
Space Complexity: O(2^n) for the DP map.
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5
using namespace std;
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> letterCount(26, 0);
for (char letter : letters)
letterCount[letter - 'a']++;
int n = words.size();
return dp(words, letterCount, score, 0, n);
}
private:
unordered_map<int, int> dpMap;
int dp(vector<string>& words, vector<int>& letterCount, vector<int>& score, int mask, int n) {
if (dpMap.count(mask)) return dpMap[mask];
int maxScore = 0;
for (int i = 0; i < n; ++i) {
if (!(mask & (1 << i))) {
int currScore = 0;
bool valid = true;
vector<int> lCount = letterCount;
for (char c : words[i]) {
if (--lCount[c - 'a'] < 0) {
valid = false;
break;
}
currScore += score[c - 'a'];
}
if (valid) {
maxScore = max(maxScore, currScore + dp(words, lCount, score, mask | (1 << i), n));
}
}
}
return dpMap[mask] = maxScore;
}
};In this C++ solution, we use bitmask dynamic programming to keep track of which words are included in the word set. Each possible word subset is a potential solution, and we calculate its score by checking if it can be formed given the available letters and scoring accordingly.