source: https://leetcode.com/problems/maximum-score-words-formed-by-letters/description/
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
class Solution { public int maxScoreWords(String[] words, char[] letters, int[] score) { Map<String, Pair> map = new HashMap<>(); for(String word: words){ Pair p = freqAndScore(word, score); map.put(word, p); } Map<String, Integer> memo = new HashMap<>(); int[] avail = available(letters); return dfs(words, avail, map, 0, memo); } private int dfs(String[] words, int[] avail, Map<String, Pair> map, int index, Map<String, Integer> memo){ if(index>= words.length){ return 0; } String key = index+":"+Arrays.toString(avail); if(memo.containsKey(key)) return memo.get(key); int max = Integer.MIN_VALUE; //Either you can pick the word String word = words[index]; Pair p = map.get(word); if(isValid(avail, p.freq)){ remove(avail, p.freq); max = Math.max(max, p.score+dfs(words, avail, map, index+1, memo)); add(avail, p.freq); } //or don't pick the word max = Math.max(max, dfs(words, avail, map, index+1, memo)); memo.put(key, max); return max; } private Pair freqAndScore(String word, int[] score){ int s = 0; char[] arr = word.toCharArray(); int[] freq = new int[26]; for(char c: arr){ s = s+score[c-'a']; freq[c-'a']++; } return new Pair(s, freq); } private int[] available(char[] letters){ int[] freq = new int[26]; for(char letter: letters){ freq[letter-'a']++; } return freq; } //check if a word can be constructed from the remaining characters private boolean isValid(int[] avail, int[] freq){ for(int i=0;i<26;i++){ if(avail[i] < freq[i]){ return false; } } return true; } private void remove(int[] avail, int[] freq){ for(int i=0;i<26;i++){ avail[i] = avail[i] - freq[i]; } } private void add(int[] avail, int[] freq){ for(int i=0;i<26;i++){ avail[i] = avail[i] + freq[i]; } } static class Pair { private int score; private int[] freq; public Pair(int score, int[] freq){ this.score = score; this.freq = freq; } } } |