Algorithm
Problem Name: 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.
Example 3:
Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0] Output: 0 Explanation: Letter "e" can only be used once.
Constraints:
1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i]
,letters[i]
contains only lower case English letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const maxScoreWords = function (words, letters, score) {
const points = new Map()
const count = Array(26).fill(0)
for (let w of letters) {
count[w.charCodeAt(0) - 97] = ~~count[w.charCodeAt(0) - 97] + 1
}
return dfs(count, 0)
function dfs(count, index) {
if (index >= words.length) {
return 0
}
const x = dfs(count, index + 1)
const copy = [...count]
let point = 0
let isValid = true
for (let w of words[index]) {
let k = w.charCodeAt(0) - 97
copy[k]--
point += score[k]
if (copy[k] < 0) isValid = false
}
return Math.max(x, isValid ? point + dfs(copy, index + 1) : 0)
}
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
from collections import Counter as cnt
class Solution:
def maxScoreWords(self, w: List[str], l: List[str], s: List[int]) -> int:
def dfs(use, i):
return (
use
and i < len(w)
and max(
dfs(use, i + 1),
not cnt(w[i]) - use
and sum(s[ord(c) - ord("a")] for c in w[i])
+ dfs(use - cnt(w[i]), i + 1),
)
)
return int(dfs(cnt(l), 0))
Copy The Code &
Try With Live Editor
Input
Output