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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaxScoreWords(string[] words, char[] letters, int[] score) {
6 Dictionary<char, int> freq = new Dictionary<char, int>();
7 foreach (var letter in letters) {
8 if (freq.ContainsKey(letter)) freq[letter]++;
9 else freq[letter] = 1;
10 }
11
12 return Backtrack(words, freq, score, 0);
13 }
14
15 private int Backtrack(string[] words, Dictionary<char, int> freq, int[] score, int index) {
16 if (index == words.Length) return 0;
17
18 int skip = Backtrack(words, freq, score, index + 1);
19
20 int wordScore = 0;
21 bool canForm = true;
22 var tempFreq = new Dictionary<char, int>();
23
24 foreach (var c in words[index]) {
25 if (!tempFreq.ContainsKey(c)) tempFreq[c] = 0;
26 tempFreq[c]++;
27
28 if (!freq.ContainsKey(c) || tempFreq[c] > freq[c]) {
29 canForm = false;
30 break;
31 }
32 wordScore += score[c - 'a'];
33 }
34
35 int use = 0;
36 if (canForm) {
37 foreach (var c in words[index]) freq[c]--;
38 use = wordScore + Backtrack(words, freq, score, index + 1);
39 foreach (var c in words[index]) freq[c]++;
40 }
41
42 return Math.Max(skip, use);
43 }
44}The C# solution uses dictionaries to store letter frequencies, allowing for dynamically checking if a word can be formed. The recursive backtrack function explores each combination for optimizing the score.
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.