1255. Maximum Score Words Formed by Letters
Given a list of words, list of single letters (might be repeating) and score of every character.
Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).
It is not necessary to use all characters in letters and each letter can only be used once. Score of letters ‘a’, ‘b’, ‘c’, … ,’z’ is given by score[0], score[1], … , score[25] respectively.
Example 1
Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.
Example 2
Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.
题意：这个题还是遍历一下所有可能所以和subset那题一样。
代码
class Solution {
public int maxScoreWords(String[] words, char[] letters, int[] score) {
int[] freq = new int[26];
for(char c : letters) {
freq[c - 'a']++;
}
int ret = helper(words, freq, score, 0);
return ret;
}
public int helper(String[] words, int[] freq, int[] score, int index) {
if(index >= words.length) return 0;
int max = 0;
for(int i = index; i < words.length; i++) {
boolean valid = true;
int ret = 0;
for(char c : words[i].toCharArray()) {
freq[c - 'a']--;
ret += score[c - 'a'];
if(freq[c - 'a'] < 0 ) valid = false;
}
if(valid) {
ret += helper(words, freq, score, i + 1);
max = Math.max(ret, max);
}
for(char c : words[i].toCharArray()) {
freq[c - 'a']++;
ret = 0;
}
}
return max;
}
}
bitmask 版本
class Solution {
public int maxScoreWords(String[] words, char[] letters, int[] score) {
int[] freq = new int[26];
for(char c : letters) {
freq[c - 'a']++;
}
int num = 1;
int max = 0;
for(int i = 0; i < (num << words.length); i++) {
int j = i;
int tmp = 0;
boolean valid = true;
int[] cfreq = new int[26];
int pos = 0;
for(int k = 0; k < 26; k++) cfreq[k] = freq[k];
while(j != 0) {
if((j & 1) == 1) {
for(char c : words[pos].toCharArray()) {
cfreq[c - 'a']--;
if(cfreq[c - 'a'] < 0) {
valid = false;
break;
}
tmp += score[c -'a'];
}
}
if(!valid) break;
j >>= 1;
pos++;
}
if(valid) max = Math.max(tmp, max);
}
return max;
}
}