Dado un número como una string donde algunos de los dígitos se reemplazan por un ‘$’ , la tarea es generar todos los números posibles reemplazando el ‘$’ con cualquiera de los dígitos de la string dada.
Ejemplos:
Entrada: str = “23$$”
Salida:
2322
2323
2332
2333
Entrada: str = “$45”
Salida:
445
545
Acercarse:
- Encuentre todas las combinaciones de la string reemplazando el carácter $ con cualquiera de los dígitos de la string, para esto, verifique si el carácter actual es un dígito, en caso afirmativo, almacene este carácter en una array pre[] y luego encuentre recursivamente todas sus combinaciones de lo contrario, si el carácter actual es un ‘$’ , reemplácelo con los dígitos almacenados en la array y encuentre recursivamente todas las combinaciones.
- Para encontrar todos los números posibles, inicialice el conjunto de arrays [] que almacena todos los números posibles, para generar números tome dos bucles anidados, el bucle externo es para la string de entrada y el bucle interno es para el conjunto de arrays [] que almacena todas las combinaciones posibles de los números. Inicialice el indicador booleano para comprobar si el carácter de la string de entrada ya está presente en set[] o no, si el carácter de la string de entrada ya está presente en set[], luego establezca flag = false; de lo contrario, si el indicador es verdadero, mueva el carácter actual de la string de entrada para establecer [] y encontrar recursivamente todas las combinaciones de la string de entrada y almacenarla en la array set []. Finalmente imprima cada número de la array set[]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 20
#define DIGITS 10
// Array to store all the
// possible numbers
string st(DIGITS,'0');
// Index to st[] element
int ed;
// Function to find all the combinations
// of the string by replacing '$' with
// the other digits of the string
void combinations(string& num, string& pre, int curr, int lvl)
{
// Check if current length is less than
// the length of the input string
if (curr < (int)num.length()) {
// If current character is a digit
// then store digit into pre[] and
// recursively find all the combinations
if (num[curr] >= '0' && num[curr] <= '9') {
pre[lvl] = num[curr];
combinations(num, pre, curr + 1, lvl + 1);
}
// If current character is a '$' then replace
// it with the other digits of the string and
// recursively find all the combinations
// Else go to the next character and
// recursively find all the combinations
else if (num[curr] == '$')
for (int i = 0; i < ed; i++) {
pre[lvl] = st[i];
combinations(num, pre, curr + 1, lvl + 1);
}
else
combinations(num, pre, curr + 1, lvl);
}
// Print the array pre[]
else {
pre[lvl] = '\0';
cout << pre << '\n';
}
}
// Function to find all the numbers formed
// from the input string by replacing '$' with
// all the digits of the input string
int findNumUtil(string& num)
{
// Array that stores the digits before
// the character $ in the input string
string pre((int)num.length(),'0');
ed = 0;
// Traverse the input string and check if
// the current character is a digit
// if it is then set flag to true
for (int i = 0; i < num.length(); i++)
if (num[i] >= '0' && num[i] <= '9') {
bool flag = true;
// Check if current character of the input
// string is already present in the array set[]
// then set flag to false
for (int j = 0; j < ed; j++)
if (st[j] == num[i])
flag = false;
// Flag is true then store the character
// into st[] and recursively find all
// the combinations of numbers and store
// it in the st[] array
if (flag == true)
st[ed++] = num[i];
}
combinations(num, pre, 0, 0);
return 0;
}
// Function to print all the combinations
// of the numbers by replacing '$' with
// the other digits of the input string
int findNum(string& num, vector<int>& result_count)
{
int i;
if (num[i]) {
result_count[i] = findNumUtil(num);
return (result_count[i]);
}
return 0;
}
// Driver code
int main()
{
string num;
num = "23$$";
vector<int> result_count(MAX);
findNum(num, result_count);
return 0;
}
C
// C implementation of the approach
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#define MAX 20
#define DIGITS 10
// Array to store all the
// possible numbers
char set[DIGITS];
// Index to set[] element
int end;
// Function to find all the combinations
// of the string by replacing '$' with
// the other digits of the string
void combinations(char* num, char* pre, int curr, int lvl)
{
// Check if current length is less than
// the length of the input string
if (curr < strlen(num)) {
// If current character is a digit
// then store digit into pre[] and
// recursively find all the combinations
if (num[curr] >= '0' && num[curr] <= '9') {
pre[lvl] = num[curr];
combinations(num, pre, curr + 1, lvl + 1);
}
// If current character is a '$' then replace
// it with the other digits of the string and
// recursively find all the combinations
// Else go to the next character and
// recursively find all the combinations
else if (num[curr] == '$')
for (int i = 0; i < end; i++) {
pre[lvl] = set[i];
combinations(num, pre, curr + 1, lvl + 1);
}
else
combinations(num, pre, curr + 1, lvl);
}
// Print the array pre[]
else {
pre[lvl] = '\0';
printf("%s\n", pre);
}
}
// Function to find all the numbers formed
// from the input string by replacing '$' with
// all the digits of the input string
int findNumUtil(char num[])
{
// Array that stores the digits before
// the character $ in the input string
char pre[MAX];
end = 0;
// Traverse the input string and check if
// the current character is a digit
// if it is then set flag to true
for (int i = 0; i < strlen(num); i++)
if (num[i] >= '0' && num[i] <= '9') {
bool flag = true;
// Check if current character of the input
// string is already present in the array set[]
// then set flag to false
for (int j = 0; j < end; j++)
if (set[j] == num[i])
flag = false;
// Flag is true then store the character
// into set[] and recursively find all
// the combinations of numbers and store
// it in the set[] array
if (flag == true)
set[end++] = num[i];
}
combinations(num, pre, 0, 0);
return 0;
}
// Function to print all the combinations
// of the numbers by replacing '$' with
// the other digits of the input string
int findNum(char* num, int* result_count)
{
int i;
if (num[i]) {
result_count[i] = findNumUtil(num);
return (result_count[i]);
}
return 0;
}
// Driver code
int main()
{
char num[MAX] = "23$$";
int result_count[MAX];
findNum(num, result_count);
return 0;
}
Python3
# Python3 implementation of the approach
MAX=20
DIGITS=10
# Array to store all the
# possible numbers
st=['0']*DIGITS
pre=[]
# Index to st[] element
ed=0
# Function to find all the combinations
# of the string by replacing '$' with
# the other digits of the string
def combinations(curr, lvl):
global num,pre
# Check if current length is less than
# the length of the input string
if (curr < len(num)):
# If current character is a digit
# then store digit into pre[] and
# recursively find all the combinations
if (num[curr] >= '0' and num[curr] <= '9'):
pre[lvl] = num[curr]
combinations(curr + 1, lvl + 1)
# If current character is a '$' then replace
# it with the other digits of the string and
# recursively find all the combinations
# Else go to the next character and
# recursively find all the combinations
elif (num[curr] == '$'):
for i in range(ed):
pre[lvl] = st[i]
combinations(curr + 1, lvl + 1)
else:
combinations(curr + 1, lvl)
# Print array pre[]
else:
print(''.join(pre))
# Function to find all the numbers formed
# from the input string by replacing '$' with
# all the digits of the input string
def findNumUtil():
# Array that stores the digits before
# the character $ in the input string
global pre,ed
pre=['0']*len(num)
ed = 0
# Traverse the input string and check if
# the current character is a digit
# if it is then set flag to True
for i in range(len(num)):
if (num[i] >= '0' and num[i] <= '9'):
flag = True
# Check if current character of the input
# string is already present in the array set[]
# then set flag to False
for j in range(ed):
if (st[j] == num[i]):
flag = False
# Flag is True then store the character
# into st[] and recursively find all
# the combinations of numbers and store
# it in the st[] array
if flag:
st[ed] = num[i]
ed+=1
combinations(0, 0)
return 0
# Function to print all the combinations
# of the numbers by replacing '$' with
# the other digits of the input string
def findNum(result_count):
i=0
if (num[i]):
result_count[i] = findNumUtil()
return (result_count[i])
return 0
# Driver code
if __name__ == '__main__':
num = "23$$"
result_count=[0]*MAX
findNum(result_count)
Producción
2322 2323 2332 2333
enfoque basado en biblioteca/conjunto de datos incorporado: –
C++
#include <bits/stdc++.h>
using namespace std;
// stores all possible non-repetitive combinations
// of string by replacing ‘$’ with any
// other digit from the string
unordered_set<string> possible_comb;
void combinations(string s,int i,int n)
{
if(i==n)
return;
// to check whether a string is
// valid combination
bool is_combination = true;
for(int i=0;i<(int)s.length();i++)
{
if(s[i]=='$')
{
is_combination = false;
break;
}
}
if(is_combination && possible_comb.find(s)==possible_comb.end())
{
possible_comb.insert(s);
return;
}
for(int i=0;i<n;i++)
{
if(s[i]=='$')
{
for(int j=0;j<n;j++)
{
if(s[j]!='$')
{
// replace the character having '$'
// with one of the digit from the
// string and recur in the combination
// function
s[i] = s[j];
combinations(s,j,n);
s[i] = '$';
}
}
}
}
}
int main() {
string s;
s = "23$$";
int len = (int)s.size();
combinations(s,0,len);
for(auto x:possible_comb)
{
cout << x << '\n';
}
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// stores all possible non-repetitive combinations
// of string by replacing ‘$’ with any
// other digit from the string
static HashSet<String> possible_comb = new HashSet<>();
static void combinations(String s,int k,int n)
{
if(k==n)
return;
// to check whether a string is
// valid combination
boolean is_combination = true;
for(int i=0;i< s.length();i++)
{
if(s.charAt(i)=='$')
{
is_combination = false;
break;
}
}
if(is_combination && possible_comb.contains(s)== false)
{
possible_comb.add(s);
return;
}
for(int i=0;i<n;i++)
{
if(s.charAt(i)=='$')
{
for(int j=0;j<n;j++)
{
if(s.charAt(j)!='$')
{
// replace the character having '$'
// with one of the digit from the
// string and recur in the combination
// function
s = s.substring(0, i) + s.charAt(j) + s.substring(i+1);
combinations(s,j,n);
s = s.substring(0, i) + '$' + s.substring(i+1);
}
}
}
}
}
// Driver Code
public static void main(String args[])
{
String s = "23$$";
int len = s.length();
combinations(s,0,len);
for(String x:possible_comb)
{
System.out.println(x);
}
}
}
// This code is contributed by shinjanpatra.
Python3
# stores all possible non-repetitive combinations
# of string by replacing ‘$’ with any
# other digit from the string
possible_comb=set()
def combinations(s,i,n):
list_s=list(s)
if(i==n):
return
# to check whether a string is
# valid combination
is_combination = True
for i in range(len(s)):
if(s[i]=='$'):
is_combination = False
break
if(is_combination and s not in possible_comb):
possible_comb.add(s)
return
for i in range(n):
if(s[i]=='$'):
for j in range(n):
if(s[j]!='$'):
# replace the character having '$'
# with one of the digit from the
# string and recur in the combination
# function
list_s[i] = list_s[j]
combinations(''.join(list_s),j,n)
list_s[i] = '$'
if __name__ == '__main__':
s = "23$$"
combinations(s,0,len(s))
for x in possible_comb:
print(x)
Javascript
<script>
// stores all possible non-repetitive combinations
// of string by replacing ‘$’ with any
// other digit from the string
let possible_comb = new Set();
function combinations(s, i, n)
{
if(i==n)
return;
// to check whether a string is
// valid combination
let is_combination = true;
for(let i = 0; i < s.length; i++)
{
if(s[i] == '$')
{
is_combination = false;
break;
}
}
if(is_combination && possible_comb.has(s)==false)
{
possible_comb.add(s);
return;
}
for(let i = 0; i < n; i++)
{
if(s[i] == '$')
{
for(let j = 0; j < n; j++)
{
if(s[j] != '$')
{
// replace the character having '$'
// with one of the digit from the
// string and recur in the combination
// function
let c = s[j];
s = s.substring(0,i) + c + s.substring(i+1)
combinations(s, j, n);
s = s.substring(0,i) + '$' + s.substring(i+1)
}
}
}
}
}
// driver code
let s;
s = "23$$";
let len = s.length;
combinations(s, 0, len);
for(let x of possible_comb)
{
document.write(x,"</br>");
}
// This code is contributed by shinjanpatra.
</script>
Producción
2333 2332 2322 2323
Complejidad de tiempo: – O (n ^ x) donde x es el número de instancias de $en la string y n es la longitud de la string
Espacio Auxiliar:- O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA