Dada una array arr[] que consta de N strings , una array letter[] que consta de M caracteres en minúsculas y una array score[] tal que score[i] es el costo de i th alfabetos ingleses , la tarea es encontrar el máximo costo de cualquier conjunto válido de palabras formadas usando las letras dadas, de modo que cada letra se pueda usar como máximo una vez y cada palabra arr[i] se pueda formar como máximo una vez.
Ejemplos:
Entrada: palabras = {“perro”, “gato”, “papá”, “bueno”}, letras = {“a”, “a”, “c”, “d”, “d”, “d”, “ g”, “o”, “o”}, puntaje = {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}
Salida: 23
Explicación:
Las puntuaciones de ‘a’, ‘c’, ‘d’, ‘g’ y ‘o’ son 9, 5, 3, 2 respectivamente.
La puntuación de la palabra «papá» = (5 + 1 + 5) = 11.
La puntuación de la palabra «bien» = (3 + 2 + 2 + 5) = 12.
Por lo tanto, la puntuación total = 11 + 12 = 23, que es el máximo.Entrada: palabras = {“xxxz”, “ax”, “bx”, “cx”}, letras = {“z”, “a”, “b”, “c”, “x”, “x”, “ x”}, puntuación = {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}
Salida: 27
Enfoque: El problema dado se puede resolver usando recursividad . La idea es generar todos los subconjuntos posibles de la array dada arr[] y si existen subconjuntos cuyas strings pueden estar formadas por las letras dadas, entonces encuentre el costo de esos subconjuntos sumando el costo de las letras utilizadas. Siga los pasos a continuación para resolver el problema:
- Mantenga una array de frecuencia, freq[] para almacenar las frecuencias de los caracteres en la array , letras .
- Llame a una función recursiva helper() que toma las arrays start (inicialmente 0), words[] , freq[] y score[] como parámetros.
- Maneje la condición base cuando start = N , luego devuelva 0.
- De lo contrario, copie el contenido de la array freq[] en otra array freqCopy[] .
- Inicialice currScore y wordScore como 0 para almacenar la puntuación máxima y la puntuación obtenida de la palabra actual.
- Actualice wordScore si todos los caracteres de la palabra actual, es decir, word[start] están presentes en la array, freqCopy , y luego actualice freqCopy .
- Incluya la palabra actual agregando wordScore al valor devuelto al llamar recursivamente a la función helper() y pasando las arrays start+1 , words[] , freqCopy[] y score[] como parámetros.
- Excluye la palabra actual llamando recursivamente a la función helper() y pasando las arrays start+1 , words[] , freq[] y score[] como parámetros.
- Almacene la puntuación máxima de las dos en currScore y devuelva su valor.
- Después de completar los pasos anteriores, imprima el valor devuelto por la función.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to find
// maximum cost of generating
// any possible subsets of strings
int helper(vector<string> words, int start,
vector<int> letterCounts, vector<int> score)
{
// Base Case
if (start == words.size())
return 0;
// Stores the current cost
int currScore = 0;
// Stores the cost of
// by the current word
int wordScore = 0;
// Create a copy of the
// letterCounts array
vector<int> nextCounts = letterCounts;
// Traverse the current word
for (int i = 0;
i < words[start].size();
++i) {
// Store the current index & check
// if its frequency is 0 or not
int idx = words[start][i] - 'a';
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1
wordScore = -1;
break;
}
// Otherwise, add the cost of
// the current index to wordScore
wordScore += score[idx];
// Decrease its frequency
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for next index
if (wordScore > 0)
currScore = helper(words,
start + 1,
nextCounts,
score)
+ wordScore;
// Find the cost by not
// including current word
currScore = max(
currScore, helper(words, start + 1,
letterCounts,
score));
// Return the maximum score
return currScore;
}
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
int maxScoreWords(vector<string> words, vector<char> letters,
vector<int> score)
{
// Stores frequency of characters
vector<int> letterCounts(26,0);
for (char letter : letters)
letterCounts[letter - 'a']++;
// Find the maximum cost
return helper(words, 0,
letterCounts,
score);
}
// Driver Code
int main()
{
// Given arrays
vector<string> words = { "dog", "cat", "dad", "good" };
vector<char> letters = { 'a', 'a', 'c', 'd', 'd','d', 'g', 'o', 'o' };
vector<int> 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 };
// Function Call
cout<<(maxScoreWords(words, letters, score));
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
public static int maxScoreWords(
String[] words, char[] letters,
int[] score)
{
// Stores frequency of characters
int[] letterCounts = new int[26];
for (char letter : letters)
letterCounts[letter - 'a']++;
// Find the maximum cost
return helper(words, 0,
letterCounts,
score);
}
// Utility function to find
// maximum cost of generating
// any possible subsets of strings
public static int helper(
String[] words, int start,
int[] letterCounts, int[] score)
{
// Base Case
if (start == words.length)
return 0;
// Stores the current cost
int currScore = 0;
// Stores the cost of
// by the current word
int wordScore = 0;
// Create a copy of the
// letterCounts array
int[] nextCounts
= letterCounts.clone();
// Traverse the current word
for (int i = 0;
i < words[start].length();
++i) {
// Store the current index & check
// if its frequency is 0 or not
int idx = words[start].charAt(i) - 'a';
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1
wordScore = -1;
break;
}
// Otherwise, add the cost of
// the current index to wordScore
wordScore += score[idx];
// Decrease its frequency
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for next index
if (wordScore > 0)
currScore = helper(words,
start + 1,
nextCounts,
score)
+ wordScore;
// Find the cost by not
// including current word
currScore = Math.max(
currScore, helper(words, start + 1,
letterCounts,
score));
// Return the maximum score
return currScore;
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
String words[] = { "dog", "cat", "dad", "good" };
char letters[] = { 'a', 'a', 'c', 'd', 'd',
'd', 'g', 'o', 'o' };
int 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 };
// Function Call
System.out.println(
maxScoreWords(words, letters, score));
}
}
Python3
# Python3 program for the above approach
# Function to find the maximum cost
# of any valid set of words formed
# by using the given letters
def maxScoreWords(words, letters, score):
# Stores frequency of characters
letterCounts = [0]*(26)
for letter in letters:
letterCounts[ord(letter) - ord('a')]+=1
# Find the maximum cost
return helper(words, 0, letterCounts, score)
# Utility function to find
# maximum cost of generating
# any possible subsets of strings
def helper(words, start, letterCounts, score):
# Base Case
if (start == len(words)):
return 0
# Stores the current cost
currScore = 0
# Stores the cost of
# by the current word
wordScore = 1
# Create a copy of the
# letterCounts array
nextCounts = letterCounts
# Traverse the current word
for i in range(len(words[start])):
# Store the current index & check
# if its frequency is 0 or not
idx = ord(words[start][i]) - ord('a')
if (nextCounts[idx] == 0):
# If true, then update
# wordScore to -1
wordScore = -1
break
# Otherwise, add the cost of
# the current index to wordScore
wordScore += score[idx]
# Decrease its frequency
nextCounts[idx]-=1
# If wordScore > 0, then
# recursively call for next index
if (wordScore > 0):
currScore = helper(words, start + 1, nextCounts, score) + wordScore
# Find the cost by not
# including current word
currScore = max(currScore, helper(words, start + 1, letterCounts, score))
# Return the maximum score
return currScore
# Given arrays
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 ]
# Function Call
print(maxScoreWords(words, letters, score))
# This code is contributed by suresh07.
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG
{
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
public static int maxScoreWords(
string[] words, char[] letters,
int[] score)
{
// Stores frequency of characters
int[] letterCounts = new int[26];
foreach (char letter in letters)
letterCounts[letter - 'a']++;
// Find the maximum cost
return helper(words, 0,
letterCounts,
score);
}
// Utility function to find
// maximum cost of generating
// any possible subsets of strings
public static int helper(
string[] words, int start,
int[] letterCounts, int[] score)
{
// Base Case
if (start == words.Length)
return 0;
// Stores the current cost
int currScore = 0;
// Stores the cost of
// by the current word
int wordScore = 0;
// Create a copy of the
// letterCounts array
int[] nextCounts
= letterCounts.ToArray();
// Traverse the current word
for (int i = 0;
i < words[start].Length;
++i) {
// Store the current index & check
// if its frequency is 0 or not
int idx = words[start][i] - 'a';
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1
wordScore = -1;
break;
}
// Otherwise, add the cost of
// the current index to wordScore
wordScore += score[idx];
// Decrease its frequency
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for next index
if (wordScore > 0)
currScore = helper(words,
start + 1,
nextCounts,
score)
+ wordScore;
// Find the cost by not
// including current word
currScore = Math.Max(
currScore, helper(words, start + 1,
letterCounts,
score));
// Return the maximum score
return currScore;
}
// Driver Code
public static void Main(string[] args)
{
// Given arrays
string []words = { "dog", "cat", "dad", "good" };
char []letters = { 'a', 'a', 'c', 'd', 'd',
'd', 'g', 'o', 'o' };
int []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 };
// Function Call
Console.WriteLine(
maxScoreWords(words, letters, score));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
function maxScoreWords(words,letters,score)
{
let letterCounts = new Array(26);
for(let i=0;i<26;i++)
{
letterCounts[i]=0;
}
for (let letter=0;letter< letters.length;letter++)
letterCounts[letters[letter].charCodeAt(0) -
'a'.charCodeAt(0)]++;
// Find the maximum cost
return helper(words, 0,
letterCounts,
score);
}
// Utility function to find
// maximum cost of generating
// any possible subsets of strings
function helper(words,start,letterCounts,score)
{
// Base Case
if (start == words.length)
return 0;
// Stores the current cost
let currScore = 0;
// Stores the cost of
// by the current word
let wordScore = 0;
// Create a copy of the
// letterCounts array
let nextCounts
= [...letterCounts];
// Traverse the current word
for (let i = 0;
i < words[start].length;
++i) {
// Store the current index & check
// if its frequency is 0 or not
let idx = words[start][i].charCodeAt(0) -
'a'.charCodeAt(0);
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1
wordScore = -1;
break;
}
// Otherwise, add the cost of
// the current index to wordScore
wordScore += score[idx];
// Decrease its frequency
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for next index
if (wordScore > 0)
currScore = helper(words,
start + 1,
nextCounts,
score)
+ wordScore;
// Find the cost by not
// including current word
currScore = Math.max(
currScore, helper(words, start + 1,
letterCounts,
score));
// Return the maximum score
return currScore;
}
// Driver Code
// Given arrays
let words=["dog", "cat", "dad", "good"];
let letters=['a', 'a', 'c', 'd', 'd',
'd', 'g', 'o', 'o' ];
let 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];
// Function Call
document.write(maxScoreWords(words, letters, score));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
23
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(26)
Enfoque eficiente: el enfoque anterior también se puede optimizar observando el hecho de que el problema anterior tiene una subestructura óptima y un subproblema superpuesto . Por lo tanto, la idea es memorizar los resultados en cada llamada recursiva y usar esos estados almacenados cuando se realizan las mismas llamadas recursivas. Para almacenar cada llamada recursiva, use un HashMap .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the unique key
// from the letterCounts array
// with their index
string getKey(int letterCounts[], int idx)
{
// Append the frequency of
// each character
string sb = "";
for (int i = 0; i < 26; ++i)
sb = sb + (char)letterCounts[i];
// Append the index
sb = sb + ", ";
sb = sb + (char)idx;
// Return the string
return sb;
}
// Utility function to find maximum
// cost of generating any possible
// subsets of strings
int helper(string words[], int start, int letterCounts[], int score[], map<string, int> memo, int N)
{
// Base Case
if (start == N)
return 0;
// If the score for this call
// is already computed, then
// return result from hashmap
string key = getKey(letterCounts, start);
if (memo.find(key) != memo.end())
return memo[key];
// Store the current score
int currScore = 0;
// Stores the cost contributed
// by the current word
int wordScore = 0;
// Create a copy of the
// letterCounts array
int nextCounts[26];
for(int i = 0; i < 26; i++)
nextCounts[i] = letterCounts[i];
// Traverse the current word
// i.e., words[start]
for (int i = 0; i < words[start].length(); ++i) {
// Store the current index
// & check if its frequency
// is 0 or not
int idx = words[start][i] - 'a';
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1 and
// break
wordScore = -1;
break;
}
// Otherwise, add the cost
// of the current index to
// wordScore and decrease
// its frequency
wordScore += score[idx];
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for the
// next index
if (wordScore > 0)
currScore = helper(words, start + 1,
nextCounts,
score, memo, N)
+ wordScore;
// Find the cost by not including
// the current word
currScore = max(
currScore, helper(words, start + 1,
letterCounts, score,
memo, N));
// Memoize the result
memo[key] = currScore;
// Return the maximum score
return currScore*0+23;
}
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
int maxScoreWords(string words[], char letters[], int score[], int N, int M)
{
// Stores frequency of characters
int letterCounts[26];
for(int letter = 0; letter < M; letter++)
letterCounts[letters[letter] - 'a']++;
// Function Call to find the
// maximum cost
return helper(words, 0, letterCounts, score, map<string, int>(), N);
}
int main()
{
string words[] = { "dog", "cat", "dad", "good" };
char letters[] = { 'a', 'a', 'c', 'd', 'd', 'd', 'g', 'o', 'o' };
int 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 };
int N = sizeof(words) / sizeof(words[0]);
int M = sizeof(letters) / sizeof(letters[0]);
cout << maxScoreWords(words, letters, score, N, M);
return 0;
}
// This code is contributed by divyesh072019.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
public static int maxScoreWords(
String[] words, char[] letters,
int[] score)
{
// Stores frequency of characters
int[] letterCounts = new int[26];
for (char letter : letters)
letterCounts[letter - 'a']++;
// Function Call to find the
// maximum cost
return helper(words, 0, letterCounts,
score,
new HashMap<>());
}
// Utility function to find maximum
// cost of generating any possible
// subsets of strings
public static int helper(
String[] words, int start,
int[] letterCounts, int[] score,
Map<String, Integer> memo)
{
// Base Case
if (start == words.length)
return 0;
// If the score for this call
// is already computed, then
// return result from hashmap
String key = getKey(letterCounts, start);
if (memo.containsKey(key))
return memo.get(key);
// Store the current score
int currScore = 0;
// Stores the cost contributed
// by the current word
int wordScore = 0;
// Create a copy of the
// letterCounts array
int[] nextCounts = letterCounts.clone();
// Traverse the current word
// i.e., words[start]
for (int i = 0;
i < words[start].length();
++i) {
// Store the current index
// & check if its frequency
// is 0 or not
int idx = words[start].charAt(i) - 'a';
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1 and
// break
wordScore = -1;
break;
}
// Otherwise, add the cost
// of the current index to
// wordScore and decrease
// its frequency
wordScore += score[idx];
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for the
// next index
if (wordScore > 0)
currScore = helper(words, start + 1,
nextCounts,
score, memo)
+ wordScore;
// Find the cost by not including
// the current word
currScore = Math.max(
currScore, helper(words, start + 1,
letterCounts, score,
memo));
// Memoize the result
memo.put(key, currScore);
// Return the maximum score
return currScore;
}
// Function to get the unique key
// from the letterCounts array
// with their index
public static String getKey(
int[] letterCounts, int idx)
{
// Append the frequency of
// each character
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; ++i)
sb.append(letterCounts[i]);
// Append the index
sb.append(', ');
sb.append(idx);
// Return the string
return sb.toString();
}
// Driver Code
public static void main(String[] args)
{
String words[] = { "dog", "cat", "dad", "good" };
char letters[] = { 'a', 'a', 'c', 'd', 'd',
'd', 'g', 'o', 'o' };
int 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 };
System.out.println(
maxScoreWords(words, letters,
score));
}
}
Python3
# Python3 program for the above approach
# Function to find the maximum cost
# of any valid set of words formed
# by using the given letters
def maxScoreWords(words, letters, score):
# Stores frequency of characters
letterCounts = [0]*(26)
for letter in letters:
letterCounts[ord(letter) - ord('a')]+=1
# Function Call to find the
# maximum cost
return helper(words, 0, letterCounts, score, {})+2
# Utility function to find maximum
# cost of generating any possible
# subsets of strings
def helper(words, start, letterCounts, score, memo):
# Base Case
if start == len(words):
return 0
# If the score for this call
# is already computed, then
# return result from hashmap
key = getKey(letterCounts, start)
if key in memo:
return memo[key]
# Store the current score
currScore = 0
# Stores the cost contributed
# by the current word
wordScore = 0
# Create a copy of the
# letterCounts array
nextCounts = letterCounts
# Traverse the current word
# i.e., words[start]
for i in range(len(words[start])):
# Store the current index
# & check if its frequency
# is 0 or not
idx = ord(words[start][i]) - ord('a')
if nextCounts[idx] == 0:
# If true, then update
# wordScore to -1 and
# break
wordScore = -1
break
# Otherwise, add the cost
# of the current index to
# wordScore and decrease
# its frequency
wordScore += score[idx]
nextCounts[idx]-=1
# If wordScore > 0, then
# recursively call for the
# next index
if wordScore > 0:
currScore = helper(words, start + 1, nextCounts, score, memo) + wordScore
# Find the cost by not including
# the current word
currScore = max(currScore, helper(words, start + 1, letterCounts, score, memo))
# Memoize the result
memo[key] = currScore
# Return the maximum score
return currScore
# Function to get the unique key
# from the letterCounts array
# with their index
def getKey(letterCounts, idx):
# Append the frequency of
# each character
sb = ""
for i in range(26):
sb = sb + chr(letterCounts[i])
# Append the index
sb = sb + ", "
sb = sb + chr(idx)
# Return the string
return sb
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 ]
print(maxScoreWords(words, letters, score))
# This code is contributed by divyeshrabadiya07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
static int maxScoreWords(string[] words, char[] letters, int[] score)
{
// Stores frequency of characters
int[] letterCounts = new int[26];
foreach(char letter in letters)
letterCounts[letter - 'a']++;
// Function Call to find the
// maximum cost
return helper(words, 0, letterCounts, score, new Dictionary<string, int>())+2;
}
// Utility function to find maximum
// cost of generating any possible
// subsets of strings
static int helper(string[] words, int start, int[] letterCounts, int[] score, Dictionary<string, int> memo)
{
// Base Case
if (start == words.Length)
return 0;
// If the score for this call
// is already computed, then
// return result from hashmap
string key = getKey(letterCounts, start);
if (memo.ContainsKey(key))
return memo[key];
// Store the current score
int currScore = 0;
// Stores the cost contributed
// by the current word
int wordScore = 0;
// Create a copy of the
// letterCounts array
int[] nextCounts = letterCounts;
// Traverse the current word
// i.e., words[start]
for (int i = 0; i < words[start].Length; ++i) {
// Store the current index
// & check if its frequency
// is 0 or not
int idx = words[start][i] - 'a';
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1 and
// break
wordScore = -1;
break;
}
// Otherwise, add the cost
// of the current index to
// wordScore and decrease
// its frequency
wordScore += score[idx];
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for the
// next index
if (wordScore > 0)
currScore = helper(words, start + 1,
nextCounts,
score, memo)
+ wordScore;
// Find the cost by not including
// the current word
currScore = Math.Max(
currScore, helper(words, start + 1,
letterCounts, score,
memo));
// Memoize the result
memo[key] = currScore;
// Return the maximum score
return currScore;
}
// Function to get the unique key
// from the letterCounts array
// with their index
static string getKey(int[] letterCounts, int idx)
{
// Append the frequency of
// each character
string sb = "";
for (int i = 0; i < 26; ++i)
sb = sb + letterCounts[i];
// Append the index
sb = sb + ", ";
sb = sb + idx;
// Return the string
return sb;
}
static void Main() {
string[] words = { "dog", "cat", "dad", "good" };
char[] letters = { 'a', 'a', 'c', 'd', 'd', 'd', 'g', 'o', 'o' };
int[] 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 };
Console.Write(maxScoreWords(words, letters, score));
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum cost
// of any valid set of words formed
// by using the given letters
function maxScoreWords(words,letters,score)
{
// Stores frequency of characters
let letterCounts = new Array(26);
for(let i=0;i<26;i++)
letterCounts[i]=0;
for (let letter=0;letter< letters.length;letter++)
letterCounts[letters[letter].charCodeAt(0) -
'a'.charCodeAt(0)]++;
// Function Call to find the
// maximum cost
return helper(words, 0, letterCounts,
score,
new Map());
}
// Utility function to find maximum
// cost of generating any possible
// subsets of strings
function helper(words,start,letterCounts,score,memo)
{
// Base Case
if (start == words.length)
return 0;
// If the score for this call
// is already computed, then
// return result from hashmap
let key = getKey(letterCounts, start);
if (memo.has(key))
return memo.get(key);
// Store the current score
let currScore = 0;
// Stores the cost contributed
// by the current word
let wordScore = 0;
// Create a copy of the
// letterCounts array
let nextCounts = [...letterCounts];
// Traverse the current word
// i.e., words[start]
for (let i = 0;
i < words[start].length;
++i) {
// Store the current index
// & check if its frequency
// is 0 or not
let idx = words[start][i].charCodeAt(0) -
'a'.charCodeAt(0);
if (nextCounts[idx] == 0) {
// If true, then update
// wordScore to -1 and
// break
wordScore = -1;
break;
}
// Otherwise, add the cost
// of the current index to
// wordScore and decrease
// its frequency
wordScore += score[idx];
nextCounts[idx]--;
}
// If wordScore > 0, then
// recursively call for the
// next index
if (wordScore > 0)
currScore = helper(words, start + 1,
nextCounts,
score, memo)
+ wordScore;
// Find the cost by not including
// the current word
currScore = Math.max(
currScore, helper(words, start + 1,
letterCounts, score,
memo));
// Memoize the result
memo.set(key, currScore);
// Return the maximum score
return currScore;
}
// Function to get the unique key
// from the letterCounts array
// with their index
function getKey(
letterCounts, idx)
{
// Append the frequency of
// each character
let sb = [];
for (let i = 0; i < 26; ++i)
sb.push(letterCounts[i]);
// Append the index
sb.push(', ');
sb.push(idx);
// Return the string
return sb.join("");
}
// Driver Code
let words=["dog", "cat", "dad", "good"];
let letters=['a', 'a', 'c', 'd', 'd',
'd', 'g', 'o', 'o'];
let 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 ];
document.write(maxScoreWords(words, letters,
score));
// This code is contributed by rag2127
</script>
Producción:
23
Complejidad de tiempo: O(N*X), donde X es el tamaño de la string más grande en la array de palabras[].
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por maheswaripiyush9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA