LeetCode-1255. Maximum Score Words Formed by Letters

LeetCode-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: 23Explanation:Score a=1, c=9, d=5, g=3, o=2Given 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: 27Explanation:Score a=4, b=4, c=4, x=5, z=10Given 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: 0Explanation: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.

题解：

class Solution {public: void dfs(int &res, int cur, vector &words, vector &dic, vector &score) { res = max(res, cur); for (int i = 0; i < words.size(); i++) { if (words[i] != "") { string tmp = words[i]; int num = 0; bool match = true; for (int j = 0; j < tmp.size(); j++) { if (dic[tmp[j] - 'a'] == 0) { match = false; } dic[tmp[j] - 'a']--; num += score[tmp[j] - 'a']; } if (match == true) { words[i] = ""; dfs(res, cur + num, words, dic, score); words[i] = tmp; } for (int j = 0; j < tmp.size(); j++) { dic[tmp[j] - 'a']++; } } } } int maxScoreWords(vector& words, vector& letters, vector& score) { vector dic(26, 0); for (int i = 0; i < letters.size(); i++) { dic[letters[i] - 'a']++; } int res = 0; dfs(res, 0, words, dic, score); return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。