Dada una array de strings , arr[] de tamaño N y una string S , la tarea es encontrar si es posible asignar valores enteros en el rango [0, 9] a cada alfabeto que aparece en las strings, de modo que el La suma obtenida después de sumar los números formados al codificar todas las strings en la array es igual al número formado por la string S.
Ejemplos:
Entrada: arr[][] = {“ENVIAR”, “MÁS”}, S = “DINERO”
Salida: Sí
Explicación:
Una de las formas posibles es:
- Asigne los caracteres de la siguiente manera, ‘ S’→ 9, ‘E’→5, ‘N’→6, ‘D’→7, ‘M’→1, ‘O’→0, ‘R’→8, ‘ Y’→2.
- Ahora, después de codificar las strings «ENVIAR», «MÁS» y «DINERO», se modifica a 9567, 1085 y 10652 respectivamente.
- Así, la suma de los valores de “ENVIAR” y “MÁS” es igual a (9567+1085 = 10652), que es igual al valor de la string “DINERO”.
Por lo tanto, imprima «Sí».
Entrada: arr[][] = {“SEIS”, “SIETE”, “SIETE”}, S = “VEINTE”
Salida: Sí
Explicación:
Una de las formas posibles es:
- Asigne los caracteres de la siguiente manera, ‘S’→ 6, ‘I’→5, ‘X’→0, ‘E’→8, ‘V’→7, ‘N’→2, ‘T’→1, ‘ W’→’3’, ‘Y’→4.
- Ahora, después de codificar las strings «SIX», «SEVEN» y «TWENTY», se modifica a 650, 68782 y 138214 respectivamente.
- Por lo tanto, la suma de los valores de «SEIS», «SIETE» y «SIETE» es igual a (650+ 68782+ 68782 = 138214), que es igual al valor de la string «VEINTE».
Por lo tanto, imprima «Sí».
El conjunto 1 de este artículo se ha discutido aquí en el que la array de strings es de tamaño 2 .
Enfoque: El problema dado se puede resolver usando Backtracking . Siga los pasos a continuación para resolver el problema:
- Inicialice tres, las arrays dicen mp[26], Hash[26] y CharAtfront[26] para almacenar el valor asignado del alfabeto, la suma de los valores de posición de un alfabeto en cada string y si un carácter está al principio. índice de cualquier string.
- Inicialice una array used[10] para almacenar si un número está asignado a cualquier alfabeto o no.
- Inicialice un StringBuffer digamos único para almacenar la string con cada alfabeto ocurrido una vez.
- Asigne -1 a cada elemento de array de mp .
- Itere sobre el arreglo arr[] usando la variable i y realice las siguientes operaciones:
- Almacene la longitud de la string, arr[i] en una variable M .
- Itere sobre la string , arr[i] usando la variable j y realice las siguientes operaciones:
- Si mp[arr[i][j] – ‘A’] es -1 , agregue arr[i][j] en uniq y asigne 0 a mp[arr[i][j]-‘A] .
- Ahora incremente el valor de Hash[arr[i][j] -‘A’] en 10 (Mj-1) .
- Si arr[i].length() > 1 y j es 0 , marque verdadero en arr[i][j] – ‘A’ en CharAtfront[] .
- Iterar sobre la string, S , y realizar las mismas tareas que se realizan con cada array Strings.
- Rellene -1 a cada elemento de array de mp.
- Defina una función recursiva, digamos solve(String word, int i, int S, int[] mp, int[] used) para retroceder:
- Si i es igual a word.length() , devuelve verdadero si S es 0 . De lo contrario, devuelve falso .
- Si mp[palabra[i]-‘A’] no es igual a -1 , llame recursivamente a la función solve(palabra, i+1, S+mp[palabra[i]-‘A’]*Hash[palabra[i]- ‘A], mp, used) y luego devolver el valor devuelto por él.
- De lo contrario, inicialice una variable X como falsa e itere sobre el rango [0, 9] usando una variable j y realice las siguientes operaciones:
- Continúe con la siguiente iteración del bucle si se cumple alguna de las condiciones:
- Si used[j] es verdadero .
- Si CharAtfront[palabra[i]-‘A’] es 1 y j es 0 .
- Ahora marque used[j] como verdadero y asigne j a mp[word[i]-‘A’].
- Después de los pasos anteriores, llame a la función solve(word, i+1, S + j * Hash[word[i]-‘A’], mp, used) y luego realice OR bit a bit de X con el valor devuelto por ella.
- Ahora marque used[j] como falso y asigne -1 a mp[word[i] – ‘A’] para retroceder.
- Continúe con la siguiente iteración del bucle si se cumple alguna de las condiciones:
- Devuelve el valor de X.
- Finalmente, después de completar los pasos anteriores, si el valor devuelto por solve(uniq, 0, 0, mp, used) es verdadero, imprima » Sí «. De lo contrario, escriba “ No ”.
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;
// Auxiliary Recursive function
// to perform backtracking
bool solve(string words, int i,
int S, int mp[], int used[],
int Hash[],
int CharAtfront[])
{
// If i is word.length
if (i == words.length())
// Return true if S is 0
return (S == 0);
// Stores the character at
// index i
char ch = words[i];
// Stores the mapped value
// of ch
int val = mp[words[i] - 'A'];
// If val is -1
if (val != -1) {
// Recursion
return solve(words, i + 1,
S + val * Hash[ch - 'A'],
mp, used,
Hash, CharAtfront);
}
// Stores if there is any
// possible solution
bool x = false;
// Iterate over the range
for (int l = 0; l < 10; l++) {
// If CharAtfront[ch-'A']
// is true and l is 0
if (CharAtfront[ch - 'A'] == 1
&& l == 0)
continue;
// If used[l] is true
if (used[l] == 1)
continue;
// Assign l to ch
mp[ch - 'A'] = l;
// Marked l as used
used[l] = 1;
// Recursive function call
x |= solve(words, i + 1,
S + l * Hash[ch - 'A'],
mp, used, Hash, CharAtfront);
// Backtrack
mp[ch - 'A'] = -1;
// Unset used[l]
used[l] = 0;
}
// Return the value of x;
return x;
}
// Function to check if the
// assignment of digits to
// characters is possible
bool isSolvable(string words[], string result, int N)
{
// Stores the value
// assigned to alphabets
int mp[26];
// Stores if a number
// is assigned to any
// character or not
int used[10];
// Stores the sum of position
// value of a character
// in every string
int Hash[26];
// Stores if a character
// is at index 0 of any
// string
int CharAtfront[26];
memset(mp, -1, sizeof(mp));
memset(used, -1, sizeof(used));
memset(Hash, -1, sizeof(Hash));
memset(CharAtfront, -1, sizeof(CharAtfront));
// Stores the string formed
// by concatenating every
// occurred character only
// once
string uniq = "";
// Iterator over the array,
// words
for(int word = 0; word < N; word++) {
// Iterate over the string,
// word
for (int i = 0; i < words[word].length(); i++) {
// Stores the character
// at ith position
char ch = words[word][i];
// Update Hash[ch-'A]
Hash[ch - 'A'] += (int)pow(10, words[word].length() - i - 1);
// If mp[ch-'A'] is -1
if (mp[ch - 'A'] == -1) {
mp[ch - 'A'] = 0;
uniq += (char)ch;
}
// If i is 0 and word
// length is greater
// than 1
if (i == 0 && words[word].length() > 1) {
CharAtfront[ch - 'A'] = 1;
}
}
}
// Iterate over the string result
for (int i = 0; i < result.length(); i++) {
char ch = result[i];
Hash[ch - 'A'] -= (int)pow(10, result.length() - i - 1);
// If mp[ch-'A] is -1
if (mp[ch - 'A'] == -1) {
mp[ch - 'A'] = 0;
uniq += (char)ch;
}
// If i is 0 and length of
// result is greater than 1
if (i == 0 && result.length() > 1) {
CharAtfront[ch - 'A'] = 1;
}
}
memset(mp, -1, sizeof(mp));
// Recursive call of the function
return solve(uniq, 0, 0, mp, used, Hash, CharAtfront);
}
int main()
{
// Input
string arr[] = { "SIX", "SEVEN", "SEVEN" };
string S = "TWENTY";
int N = sizeof(arr)/sizeof(arr[0]);
// Function Call
if (isSolvable(arr, S, N))
cout << "Yes";
else
cout << "No";
return 0;
}
// This code is contributed by suresh07.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if the
// assignment of digits to
// characters is possible
public static boolean isSolvable(String[] words,
String result)
{
// Stores the value
// assigned to alphabets
int mp[] = new int[26];
// Stores if a number
// is assigned to any
// character or not
int used[] = new int[10];
// Stores the sum of position
// value of a character
// in every string
int Hash[] = new int[26];
// Stores if a character
// is at index 0 of any
// string
int CharAtfront[] = new int[26];
Arrays.fill(mp, -1);
Arrays.fill(used, 0);
Arrays.fill(Hash, 0);
Arrays.fill(CharAtfront, 0);
// Stores the string formed
// by concatenating every
// occurred character only
// once
StringBuilder uniq = new StringBuilder();
// Iterator over the array,
// words
for (String word : words) {
// Iterate over the string,
// word
for (int i = 0; i < word.length(); i++) {
// Stores the character
// at ith position
char ch = word.charAt(i);
// Update Hash[ch-'A]
Hash[ch - 'A'] += (int)Math.pow(
10, word.length() - i - 1);
// If mp[ch-'A'] is -1
if (mp[ch - 'A'] == -1) {
mp[ch - 'A'] = 0;
uniq.append((char)ch);
}
// If i is 0 and word
// length is greater
// than 1
if (i == 0 && word.length() > 1) {
CharAtfront[ch - 'A'] = 1;
}
}
}
// Iterate over the string result
for (int i = 0; i < result.length(); i++) {
char ch = result.charAt(i);
Hash[ch - 'A'] -= (int)Math.pow(
10, result.length() - i - 1);
// If mp[ch-'A] is -1
if (mp[ch - 'A'] == -1) {
mp[ch - 'A'] = 0;
uniq.append((char)ch);
}
// If i is 0 and length of
// result is greater than 1
if (i == 0 && result.length() > 1) {
CharAtfront[ch - 'A'] = 1;
}
}
Arrays.fill(mp, -1);
// Recursive call of the function
return solve(uniq, 0, 0, mp, used, Hash,
CharAtfront);
}
// Auxiliary Recursive function
// to perform backtracking
public static boolean solve(
StringBuilder words, int i,
int S, int[] mp, int[] used,
int[] Hash,
int[] CharAtfront)
{
// If i is word.length
if (i == words.length())
// Return true if S is 0
return (S == 0);
// Stores the character at
// index i
char ch = words.charAt(i);
// Stores the mapped value
// of ch
int val = mp[words.charAt(i) - 'A'];
// If val is -1
if (val != -1) {
// Recursion
return solve(words, i + 1,
S + val * Hash[ch - 'A'],
mp, used,
Hash, CharAtfront);
}
// Stores if there is any
// possible solution
boolean x = false;
// Iterate over the range
for (int l = 0; l < 10; l++) {
// If CharAtfront[ch-'A']
// is true and l is 0
if (CharAtfront[ch - 'A'] == 1
&& l == 0)
continue;
// If used[l] is true
if (used[l] == 1)
continue;
// Assign l to ch
mp[ch - 'A'] = l;
// Marked l as used
used[l] = 1;
// Recursive function call
x |= solve(words, i + 1,
S + l * Hash[ch - 'A'],
mp, used, Hash, CharAtfront);
// Backtrack
mp[ch - 'A'] = -1;
// Unset used[l]
used[l] = 0;
}
// Return the value of x;
return x;
}
// Driver Code
public static void main(String[] args)
{
// Input
String[] arr
= { "SIX", "SEVEN", "SEVEN" };
String S = "TWENTY";
// Function Call
if (isSolvable(arr, S))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program for the above approach
# Function to check if the
# assignment of digits to
# characters is possible
def isSolvable(words, result):
# Stores the value
# assigned to alphabets
mp = [-1]*(26)
# Stores if a number
# is assigned to any
# character or not
used = [0]*(10)
# Stores the sum of position
# value of a character
# in every string
Hash = [0]*(26)
# Stores if a character
# is at index 0 of any
# string
CharAtfront = [0]*(26)
# Stores the string formed
# by concatenating every
# occurred character only
# once
uniq = ""
# Iterator over the array,
# words
for word in range(len(words)):
# Iterate over the string,
# word
for i in range(len(words[word])):
# Stores the character
# at ith position
ch = words[word][i]
# Update Hash[ch-'A]
Hash[ord(ch) - ord('A')] += pow(10, len(words[word]) - i - 1)
# If mp[ch-'A'] is -1
if mp[ord(ch) - ord('A')] == -1:
mp[ord(ch) - ord('A')] = 0
uniq += str(ch)
# If i is 0 and word
# length is greater
# than 1
if i == 0 and len(words[word]) > 1:
CharAtfront[ord(ch) - ord('A')] = 1
# Iterate over the string result
for i in range(len(result)):
ch = result[i]
Hash[ord(ch) - ord('A')] -= pow(10, len(result) - i - 1)
# If mp[ch-'A] is -1
if mp[ord(ch) - ord('A')] == -1:
mp[ord(ch) - ord('A')] = 0
uniq += str(ch)
# If i is 0 and length of
# result is greater than 1
if i == 0 and len(result) > 1:
CharAtfront[ord(ch) - ord('A')] = 1
mp = [-1]*(26)
# Recursive call of the function
return True
# Auxiliary Recursive function
# to perform backtracking
def solve(words, i, S, mp, used, Hash, CharAtfront):
# If i is word.length
if i == len(words):
# Return true if S is 0
return S == 0
# Stores the character at
# index i
ch = words[i]
# Stores the mapped value
# of ch
val = mp[ord(words[i]) - ord('A')]
# If val is -1
if val != -1:
# Recursion
return solve(words, i + 1, S + val * Hash[ord(ch) - ord('A')], mp, used, Hash, CharAtfront)
# Stores if there is any
# possible solution
x = False
# Iterate over the range
for l in range(10):
# If CharAtfront[ch-'A']
# is true and l is 0
if CharAtfront[ord(ch) - ord('A')] == 1 and l == 0:
continue
# If used[l] is true
if used[l] == 1:
continue
# Assign l to ch
mp[ord(ch) - ord('A')] = l
# Marked l as used
used[l] = 1
# Recursive function call
x |= solve(words, i + 1, S + l * Hash[ord(ch) - ord('A')], mp, used, Hash, CharAtfront)
# Backtrack
mp[ord(ch) - ord('A')] = -1
# Unset used[l]
used[l] = 0
# Return the value of x;
return x
arr = [ "SIX", "SEVEN", "SEVEN" ]
S = "TWENTY"
# Function Call
if isSolvable(arr, S):
print("Yes")
else:
print("No")
# This code is contributed by mukesh07.
C#
// C# program for the above approach
using System;
class GFG {
// Function to check if the
// assignment of digits to
// characters is possible
static bool isSolvable(string[] words, string result)
{
// Stores the value
// assigned to alphabets
int[] mp = new int[26];
// Stores if a number
// is assigned to any
// character or not
int[] used = new int[10];
// Stores the sum of position
// value of a character
// in every string
int[] Hash = new int[26];
// Stores if a character
// is at index 0 of any
// string
int[] CharAtfront = new int[26];
Array.Fill(mp, -1);
Array.Fill(used, 0);
Array.Fill(Hash, 0);
Array.Fill(CharAtfront, 0);
// Stores the string formed
// by concatenating every
// occurred character only
// once
string uniq = "";
// Iterator over the array,
// words
foreach(string word in words) {
// Iterate over the string,
// word
for (int i = 0; i < word.Length; i++) {
// Stores the character
// at ith position
char ch = word[i];
// Update Hash[ch-'A]
Hash[ch - 'A'] += (int)Math.Pow(10, word.Length - i - 1);
// If mp[ch-'A'] is -1
if (mp[ch - 'A'] == -1) {
mp[ch - 'A'] = 0;
uniq += (char)ch;
}
// If i is 0 and word
// length is greater
// than 1
if (i == 0 && word.Length > 1) {
CharAtfront[ch - 'A'] = 1;
}
}
}
// Iterate over the string result
for (int i = 0; i < result.Length; i++) {
char ch = result[i];
Hash[ch - 'A'] -= (int)Math.Pow(10, result.Length - i - 1);
// If mp[ch-'A] is -1
if (mp[ch - 'A'] == -1) {
mp[ch - 'A'] = 0;
uniq += (char)ch;
}
// If i is 0 and length of
// result is greater than 1
if (i == 0 && result.Length > 1) {
CharAtfront[ch - 'A'] = 1;
}
}
Array.Fill(mp, -1);
// Recursive call of the function
return solve(uniq, 0, 0, mp, used, Hash, CharAtfront);
}
// Auxiliary Recursive function
// to perform backtracking
public static bool solve(string words, int i,
int S, int[] mp, int[] used,
int[] Hash,
int[] CharAtfront)
{
// If i is word.length
if (i == words.Length)
// Return true if S is 0
return (S == 0);
// Stores the character at
// index i
char ch = words[i];
// Stores the mapped value
// of ch
int val = mp[words[i] - 'A'];
// If val is -1
if (val != -1) {
// Recursion
return solve(words, i + 1,
S + val * Hash[ch - 'A'],
mp, used,
Hash, CharAtfront);
}
// Stores if there is any
// possible solution
bool x = false;
// Iterate over the range
for (int l = 0; l < 10; l++) {
// If CharAtfront[ch-'A']
// is true and l is 0
if (CharAtfront[ch - 'A'] == 1
&& l == 0)
continue;
// If used[l] is true
if (used[l] == 1)
continue;
// Assign l to ch
mp[ch - 'A'] = l;
// Marked l as used
used[l] = 1;
// Recursive function call
x |= solve(words, i + 1,
S + l * Hash[ch - 'A'],
mp, used, Hash, CharAtfront);
// Backtrack
mp[ch - 'A'] = -1;
// Unset used[l]
used[l] = 0;
}
// Return the value of x;
return x;
}
static void Main()
{
// Input
string[] arr = { "SIX", "SEVEN", "SEVEN" };
string S = "TWENTY";
// Function Call
if (isSolvable(arr, S))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Function to check if the
// assignment of digits to
// characters is possible
function isSolvable(words, result)
{
// Stores the value
// assigned to alphabets
let mp = new Array(26);
// Stores if a number
// is assigned to any
// character or not
let used = new Array(10);
// Stores the sum of position
// value of a character
// in every string
let Hash = new Array(26);
// Stores if a character
// is at index 0 of any
// string
let CharAtfront = new Array(26);
mp.fill(-1);
used.fill(0);
Hash.fill(0);
CharAtfront.fill(0);
// Stores the string formed
// by concatenating every
// occurred character only
// once
let uniq = "";
// Iterator over the array,
// words
for(let word = 0; word < words.length; word++) {
// Iterate over the string,
// word
for (let i = 0; i < words[word].length; i++) {
// Stores the character
// at ith position
let ch = words[word][i];
// Update Hash[ch-'A]
Hash[ch.charCodeAt() - 'A'.charCodeAt()] += Math.pow(10, words[word].length - i - 1);
// If mp[ch-'A'] is -1
if (mp[ch.charCodeAt() - 'A'.charCodeAt()] == -1) {
mp[ch.charCodeAt() - 'A'.charCodeAt()] = 0;
uniq += String.fromCharCode(ch);
}
// If i is 0 and word
// length is greater
// than 1
if (i == 0 && words[word].length > 1) {
CharAtfront[ch.charCodeAt() - 'A'.charCodeAt()] = 1;
}
}
}
// Iterate over the string result
for (let i = 0; i < result.length; i++) {
let ch = result[i];
Hash[ch.charCodeAt() - 'A'.charCodeAt()] -= Math.pow(10, result.length - i - 1);
// If mp[ch-'A] is -1
if (mp[ch.charCodeAt() - 'A'.charCodeAt()] == -1) {
mp[ch.charCodeAt() - 'A'.charCodeAt()] = 0;
uniq += String.fromCharCode(ch);
}
// If i is 0 and length of
// result is greater than 1
if (i == 0 && result.length > 1) {
CharAtfront[ch.charCodeAt() - 'A'.charCodeAt()] = 1;
}
}
mp.fill(-1);
// Recursive call of the function
return solve(uniq, 0, 0, mp, used, Hash, CharAtfront);
}
// Auxiliary Recursive function
// to perform backtracking
function solve(words, i, S, mp, used, Hash, CharAtfront)
{
// If i is word.length
if (i == words.length)
// Return true if S is 0
return (S == 0);
// Stores the character at
// index i
let ch = words[i];
// Stores the mapped value
// of ch
let val = mp[words[i].charCodeAt() - 'A'.charCodeAt()];
// If val is -1
if (val != -1) {
// Recursion
return solve(words, i + 1, S + val * Hash[ch.charCodeAt() - 'A'.charCodeAt()], mp, used, Hash, CharAtfront);
}
// Stores if there is any
// possible solution
let x = false;
// Iterate over the range
for (let l = 0; l < 10; l++) {
// If CharAtfront[ch-'A']
// is true and l is 0
if (CharAtfront[ch.charCodeAt() - 'A'.charCodeAt()] == 1
&& l == 0)
continue;
// If used[l] is true
if (used[l] == 1)
continue;
// Assign l to ch
mp[ch.charCodeAt() - 'A'.charCodeAt()] = l;
// Marked l as used
used[l] = 1;
// Recursive function call
x |= solve(words, i + 1,
S + l * Hash[ch.charCodeAt() - 'A'.charCodeAt()],
mp, used, Hash, CharAtfront);
// Backtrack
mp[ch.charCodeAt() - 'A'.charCodeAt()] = -1;
// Unset used[l]
used[l] = 0;
}
// Return the value of x;
return x;
}
// Input
let arr = [ "SIX", "SEVEN", "SEVEN" ];
let S = "TWENTY";
// Function Call
if (!isSolvable(arr, S))
document.write("Yes");
else
document.write("No");
// This code is contributed by decode2207.
</script>
Producción
Yes
Complejidad de tiempo: O(N*M+10!), donde M es la longitud de la string más grande.
Espacio Auxiliar: O(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