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.
1import java.util.List;
2
3class Solution {
4 public int maxScoreWords(String[] words, char[] letters, int[] score) {
5 int[] letterCount = new int[26];
6 for (char letter : letters) {
7 letterCount[letter - 'a']++;
8 }
9
10 return backtrack(words, letterCount, score, 0);
11 }
12
13 private int backtrack(String[] words, int[] letterCount, int[] score, int index) {
14 if (index == words.length) return 0;
15
16 int skip = backtrack(words, letterCount, score, index + 1);
17
18 int wordScore = 0;
19 int[] tempCount = new int[26];
20 boolean canForm = true;
21 for (char c : words[index].toCharArray()) {
22 if (++tempCount[c - 'a'] > letterCount[c - 'a']) {
23 canForm = false;
24 break;
25 }
26 wordScore += score[c - 'a'];
27 }
28 int use = 0;
29 if (canForm) {
30 for (char c : words[index].toCharArray()) letterCount[c - 'a'] -= tempCount[c - 'a'];
31 use = wordScore + backtrack(words, letterCount, score, index + 1);
32 for (char c : words[index].toCharArray()) letterCount[c - 'a'] += tempCount[c - 'a'];
33 }
34 return Math.max(skip, use);
35 }
36}The Java solution utilizes the same backtracking logic, checking each word and deciding to include it or skip it, continuously updating available letters. This approach calculates and returns the maximum viable 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.