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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5int calculateScore(char* word, int* score) {
6 int sum = 0;
7 for (int i = 0; word[i] != '\0'; i++) {
8 sum += score[word[i] - 'a'];
9 }
10 return sum;
11}
12
13void backTrack(char** words, int wordsSize, int* letterCount, int* score, int currentScore, int* maxScore, int index) {
14 if (index == wordsSize) {
15 if (currentScore > *maxScore) *maxScore = currentScore;
16 return;
17 }
18
19 backTrack(words, wordsSize, letterCount, score, currentScore, maxScore, index + 1);
20
21 int canUseWord = 1;
22 char* word = words[index];
23 for (int i = 0; word[i] != '\0'; i++) {
24 if (letterCount[word[i] - 'a'] <= 0) {
25 canUseWord = 0;
26 break;
27 }
28 letterCount[word[i] - 'a']--;
29 }
30
31 if (canUseWord) {
32 backTrack(words, wordsSize, letterCount, score, currentScore + calculateScore(word, score), maxScore, index + 1);
33 }
34
35 for (int i = 0; word[i] != '\0'; i++) {
36 letterCount[word[i] - 'a']++;
37 }
38}
39
40int maxScoreWords(char** words, int wordsSize, char* letters, int lettersSize, int* score) {
41 int letterCount[26] = {0};
42 for (int i = 0; i < lettersSize; i++) {
43 letterCount[letters[i] - 'a']++;
44 }
45
46 int maxScore = 0;
47 backTrack(words, wordsSize, letterCount, score, 0, &maxScore, 0);
48
49 return maxScore;
50}This C implementation uses a recursive backtracking approach. Beginning with the first word, it decides whether to include the word in the count by checking the frequency available in the letters. If a word is included, its letter usage is deducted from the availability. The recursion continues to explore further possibilities. Finally, the maximum score is recorded.
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.