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 <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10words[i], letters[i] contains only lower case English letters.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.
This C implementation uses a recursive backtracking approach. Beginning with the first word, it decides whether to include the word in the count by checking the frequency available in the letters. If a word is included, its letter usage is deducted from the availability. The recursion continues to explore further possibilities. Finally, the maximum score is recorded.
C++
Java
Python
C#
JavaScript
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.
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.
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.
Python
Time Complexity: O(n * 2^n), where n is the number of words.
Space Complexity: O(2^n) for the DP map.
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking | 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. |
| Approach 2: Dynamic Programming | Time Complexity: O(n * 2^n), where n is the number of words. |
Maximum Score Words Formed By Letters - Leetcode 1255 - Python • NeetCodeIO • 10,599 views views
Watch 9 more video solutions →Practice Maximum Score Words Formed by Letters with our built-in code editor and test cases.
Practice on FleetCode