1255. Maximum Score Words Formed by Letters LeetCode Solution
In this guide, you will get 1255. Maximum Score Words Formed by Letters LeetCode Solution with the best time and space complexity. The solution to Maximum Score Words Formed by Letters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
Time Complexity: O(|\texttt{letters}| + 2^{|\texttt{words}|})
Space Complexity: O(|\texttt{letters}| + 2^{|\texttt{words}|})
1255. Maximum Score Words Formed by Letters LeetCode Solution in C++
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters,
vector<int>& score) {
vector<int> count(26);
for (const char c : letters)
++count[c - 'a'];
return dfs(words, 0, count, score);
}
private:
// Returns the maximum score you can get from words[s..n).
int dfs(const vector<string>& words, int s, vector<int>& count,
const vector<int>& 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<string>& words, int i, vector<int>& count,
const vector<int>& 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<string>& words, int i, vector<int>& count) {
for (const char c : words[i])
++count[c - 'a'];
}
}; /* code provided by PROGIEZ */
1255. Maximum Score Words Formed by Letters LeetCode Solution in Java
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);
}
// Returns the maximum score you can get from words[s..n).
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'];
}
} // code provided by PROGIEZ
1255. Maximum Score Words Formed by Letters LeetCode Solution in Python
class Solution:
def maxScoreWords(
self,
words: list[str],
letters: list[str],
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[string.ascii_lowercase.index(c)]
return earned if isValid else -1
def unuseWord(i: int) -> None:
for c in words[i]:
count[c] += 1
def dfs(s: int) -> int:
"""Returns the maximum score you can get from words[s..n)."""
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) # code by PROGIEZ
