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.
1from typing import List
2
3class Solution:
4 def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
5 from collections import Counter
6
7 freq = Counter(letters)
8
9 def backtrack(index):
10 if index == len(words):
11 return 0
12
13 skip = backtrack(index + 1)
14
15 word_score, can_form = 0, True
16 word_count = Counter(words[index])
17 for char, count in word_count.items():
18 if freq[char] < count:
19 can_form = False
20 break
21 word_score += score[ord(char) - ord('a')] * count
22
23 use = 0
24 if can_form:
25 for char, count in word_count.items():
26 freq[char] -= count
27 use = word_score + backtrack(index + 1)
28 for char, count in word_count.items():
29 freq[char] += count
30
31 return max(skip, use)
32
33 return backtrack(0)In this Python solution, we make use of the Counter class to manage the frequency of letters. The backtrack function increments and decrements these counts depending on whether the current word is added for scoring. It recursively finds the best score outcome.
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.