Dada una array de strings , palabras[] de tamaño M y una string de destino de tamaño N. La tarea es encontrar el número mínimo de palabras requeridas para deletrear el objetivo de la string cortando letras individuales de la colección de palabras y reorganizándolas, siempre que haya cantidades infinitas de cada palabra. Si no es posible, imprima -1.
Ejemplos:
Enfoque: La idea es utilizar backtracking . Siga los pasos para resolver el problema:
- Declare una array 2D , digamos countMap[][], donde countMap[i][j] almacena el recuento de j -ésimo carácter en i -ésima string.
- Declare una array charAvavilable[26], que indica el recuento actual de caracteres disponibles.
- Defina una función recursiva que tome el índice actual, i (inicialmente 0) de la string, objetivo como entrada.
- Si el conteo actual es mayor que el conteo general, devuelva . Además, si el índice actual, i es igual a N , actualice el recuento general y devuelva .
- Si hay una ocurrencia de target[i] en charAvailable[] ,
- Disminuya la ocurrencia del carácter target[i] en charAvailable[] .
- Llame recursivamente al índice i+1 , actualizando simultáneamente el conteo por 1.
- Incrementa la aparición del carácter target[i] en 1 después de la llamada de función para retroceder .
- De lo contrario, itere el countMap[][] para encontrar la aparición de target[i] . Si la encuentra, llame recursivamente a la función actualizando el conteo en 1 y también realice el paso de retroceso después de la llamada a la función.
- Escriba el número mínimo de palabras requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// countMap[][] to store
// count of characters
vector<vector<int> > countMap;
int cnt = INT_MAX;
// Function to get minimum number of
// stickers for a particular state
void count(int curCnt, int pos, vector<int>charAvailable,
string target, vector<string> stickers)
{
// If an optimal solution is
// already there, return
if (curCnt >= cnt)
return;
int m = stickers.size();
int n = target.size();
// If Target has been constructed
// update cnt and return
if (pos == n)
{
cnt = min(cnt, curCnt);
return;
}
char c = target[pos];
if (charAvailable > 0)
{
// Update charAvailable[]
charAvailable--;
// Recursizevely function call
// for (pos + 1)
count(curCnt, pos + 1, charAvailable,
target, stickers);
// Update charAvailable[]
charAvailable++;
}
else
{
for(int i = 0; i < m; i++)
{
if (countMap[i] == 0)
continue;
// Update charAvailable[]
for(int j = 0; j < 26; j++)
{
charAvailable[j] += countMap[i][j];
}
// Recursizeve Call
count(curCnt + 1, pos, charAvailable,
target, stickers);
// Update charAvailable[]
for(int j = 0; j < 26; j++)
{
charAvailable[j] -= countMap[i][j];
}
}
}
}
// Function to find the minimum
// number of stickers
int minStickers(vector<string> stickers,
string target)
{
// Base Case
if (target == "")
return -1;
if (target.size() == 0)
return 0;
if (stickers.size() == 0)
return -1;
int m = stickers.size();
countMap.resize(m, vector<int>(26, 0));
// Fill the countMap Array
for(int i = 0; i < stickers.size(); i++)
{
string s = stickers[i];
for(char c : s)
{
countMap[i]++;
}
}
// Recusizeve function call to get
// minimum number of stickers
vector<int> temp(26);
count(0, 0, temp, target, stickers);
return cnt == INT_MAX ? -1 : cnt;
}
// Driver Code
int main()
{
// Given Input
vector<string> str = {"with", "example", "science"};
string target = "thehat";
// Function Call
int Result = minStickers(str, target);
// Print the result
cout << Result;
}
// This code is contributed by mohit kumar 29
Java
// Java program of the above approach
import java.io.*;
import java.util.*;
class Sol {
// countMap[][] to store
// count of characters
int[][] countMap;
int cnt = Integer.MAX_VALUE;
// Function to find the minimum
// number of stickers
public int minStickers(String[] stickers
, String target)
{
// Base Case
if (target == null)
return -1;
if (target.length() == 0)
return 0;
if (stickers == null || stickers.length == 0)
return -1;
int m = stickers.length;
countMap = new int[m][26];
// Fill the countMap Array
for (int i = 0; i < stickers.length; i++) {
String s = stickers[i];
for (char c : s.toCharArray()) {
countMap[i]++;
}
}
// Recursive function call to get
// minimum number of stickers
count(0, 0, new int[26], target, stickers);
return cnt == Integer.MAX_VALUE ? -1 : cnt;
}
// Function to get minimum number of
// stickers for a particular state
private void count(int curCnt, int pos,
int[] charAvailable, String target,
String[] stickers)
{
// If an optimal solution is
// already there, return
if (curCnt >= cnt)
return;
int m = stickers.length;
int n = target.length();
// If Target has been constructed
// update cnt and return
if (pos == n) {
cnt = Math.min(cnt, curCnt);
return;
}
char c = target.charAt(pos);
if (charAvailable > 0) {
// Update charAvailable[]
charAvailable--;
// Recursively function call
// for (pos + 1)
count(curCnt, pos + 1, charAvailable, target,
stickers);
// Update charAvailable[]
charAvailable++;
}
else {
for (int i = 0; i < m; i++) {
if (countMap[i] == 0)
continue;
// Update charAvailable[]
for (int j = 0; j < 26; j++) {
charAvailable[j] += countMap[i][j];
}
// Recursive Call
count(curCnt + 1, pos, charAvailable,
target, stickers);
// Update charAvailable[]
for (int j = 0; j < 26; j++) {
charAvailable[j] -= countMap[i][j];
}
}
}
}
}
class GFG {
// Driver Code
public static void main(String[] args)
{
Sol st = new Sol();
// Given Input
String[] str = { "with", "example", "science" };
String target = "thehat";
// Function Call
int Result = st.minStickers(str, target);
// Print the result
System.out.println(Result);
}
}
Producción:
3
Complejidad de tiempo: O(M*26*2 N )
Espacio auxiliar: O(M*26)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA