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.
Solution: Combination
Time complexity: O(2^n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) { vector<int> counts(26); vector<int> scores(words.size()); for (char c : letters) ++counts[c - 'a']; for (int i = 0; i < words.size(); ++i) for (char c : words[i]) scores[i] += score[c - 'a']; int ans = 0; function<void(int, int)> dfs = [&](int s, int cur) { if (cur > ans) ans = cur; for (int i = s; i < words.size(); ++i) { bool valid = true; for (char c : words[i]) valid &= --counts[c - 'a'] >= 0; if (valid) dfs(i + 1, cur + scores[i]); for (char c : words[i]) ++counts[c - 'a']; } }; dfs(0, 0); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment