# 1255. Maximum Score Words Formed by Letters

• Time: $O(|\texttt{letters}| + 2^{|\texttt{words}|})$
• Space: $O(|\texttt{letters}| + 2^{|\texttt{words}|})$
  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 class Solution { public: int maxScoreWords(vector& words, vector& letters, vector& score) { vector count(26); for (const char c : letters) ++count[c - 'a']; return dfs(words, 0, count, score); } private: // Max score you can get from words[s:] int dfs(const vector& words, int s, vector& count, const vector& score) { int ans = 0; for (int i = s; i < words.size(); ++i) { const int earned = useWord(words, i, count, score); if (earned > 0) ans = max(ans, earned + dfs(words, i + 1, count, score)); unuseWord(words, i, count); } return ans; } int useWord(const vector& words, int i, vector& count, const vector& score) { bool isValid = true; int earned = 0; for (const char c : words[i]) { if (--count[c - 'a'] < 0) isValid = false; earned += score[c - 'a']; } return isValid ? earned : -1; } void unuseWord(const vector& words, int i, vector& count) { for (const char c : words[i]) ++count[c - 'a']; } }; 
  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 class Solution { public int maxScoreWords(String[] words, char[] letters, int[] score) { int[] count = new int[26]; for (final char c : letters) ++count[c - 'a']; return dfs(words, 0, count, score); } // Max score you can get from words[s:] private int dfs(String[] words, int s, int[] count, int[] score) { int ans = 0; for (int i = s; i < words.length; ++i) { final int earned = useWord(words, i, count, score); if (earned > 0) ans = Math.max(ans, earned + dfs(words, i + 1, count, score)); unuseWord(words, i, count); } return ans; } int useWord(String[] words, int i, int[] count, int[] score) { boolean isValid = true; int earned = 0; for (final char c : words[i].toCharArray()) { if (--count[c - 'a'] < 0) isValid = false; earned += score[c - 'a']; } return isValid ? earned : -1; } void unuseWord(String[] words, int i, int[] count) { for (final char c : words[i].toCharArray()) ++count[c - 'a']; } } 
  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 class Solution: def maxScoreWords(self, words: List[str], letters: List[chr], score: List[int]) -> int: count = collections.Counter(letters) def useWord(i: int) -> int: isValid = True earned = 0 for c in words[i]: count[c] -= 1 if count[c] < 0: isValid = False earned += score[ord(c) - ord('a')] return earned if isValid else -1 def unuseWord(i: int) -> None: for c in words[i]: count[c] += 1 # Max score you can get from words[s:] def dfs(s: int) -> int: ans = 0 for i in range(s, len(words)): earned = useWord(i) if earned > 0: ans = max(ans, earned + dfs(i + 1)) unuseWord(i) return ans return dfs(0)