Dada una string S que consta de N caracteres y una array M[] de pares de caracteres tal que cualquier carácter M[i][0] se puede reemplazar con el carácter M[i][1] en la string S , la tarea es para generar todas las strings posibles formadas al reemplazar algunos caracteres de la string con sus respectivos símbolos en la array M[] .
Ejemplos:
Entrada: S = “aBc”, M = {‘a’ : ‘$’, ‘B’ : ‘#’, ‘c’ : ‘^’}
Salida:
aBc
aB^
a#c
a#^
$Bc
$B^
$#c
$#^Entrada: S = “a”, M={‘a’ : ‘$’}
Salida:
a
$
Enfoque: el problema dado se puede resolver utilizando Backtracking para generar todas las strings posibles al reemplazar cada carácter con el carácter asignado en la array M[] . Siga los pasos a continuación para resolver el problema:
- Almacene todos los pares de caracteres asignados en la array M[] en un mapa , digamos Mapa .
- Defina una función recursiva, digamos generateLetters(S, P) , donde S es la string modificada y P es el índice del carácter actual:
- Verifique el caso base, es decir, si el índice P es igual a la N , imprima la string S y regrese.
- No cambie el carácter actual y llame recursivamente a la función , generateLetters(S, P + 1) .
- Ahora, reemplace el carácter, S[P] con el símbolo respectivo en el mapa M y llame a la función, generateLetters(S, P+1) .
- Después de completar los pasos anteriores, llame a la función generar letras (S, 0) para imprimir todas las strings posibles.
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 generate all possible
// string by replacing the characters
// with mapped symbols
void generateLetters(string S, int P,
unordered_map<char, char> M)
{
// Base Case
if (P == S.size()) {
cout << S << "\n";
return;
}
// Function call with the P-th
// character not replaced
generateLetters(S, P + 1, M);
// Replace the P-th character
S[P] = M[S[P]];
// Function call with the P-th
// character replaced
generateLetters(S, P + 1, M);
return;
}
// Driver Code
int main()
{
string S = "aBc";
unordered_map<char, char> M;
M['a'] = '$';
M['B'] = '#';
M['c'] = '^';
M['d'] = '&';
M['1'] = '*';
M['2'] = '!';
M['E'] = '@';
// Function Call
generateLetters(S, 0, M);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
class GFG{
// Function to generate all possible
// string by replacing the characters
// with mapped symbols
public static void generateLetters(String S, int P, HashMap<Character, Character> M)
{
// Base Case
if (P == S.length()) {
System.out.println(S);
return;
}
// Function call with the P-th
// character not replaced
generateLetters(S, P + 1, M);
// Replace the P-th character
S = S.substring(0, P) + M.get(S.charAt(P)) + S.substring(P + 1);
// Function call with the P-th
// character replaced
generateLetters(S, P + 1, M);
return;
}
// Driver Code
public static void main(String args[])
{
String S = "aBc";
HashMap<Character, Character> M = new HashMap<Character, Character>();
M.put('a', '$');
M.put('B', '#');
M.put('c', '^');
M.put('d', '&');
M.put('1', '*');
M.put('2', '!');
M.put('E', '@');
// Function Call
generateLetters(S, 0, M);
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python program for the above approach
# Function to generate all possible
# string by replacing the characters
# with mapped symbols
def generateLetters(S, P, M):
# Base Case
if (P == len(S)):
print(S);
return
# Function call with the P-th
# character not replaced
generateLetters(S, P + 1, M);
# Replace the P-th character
S = S.replace(S[P], M[S[P]])
# Function call with the P-th
# character replaced
generateLetters(S, P + 1, M);
# Driver Code
S = "aBc";
M = {};
M['a'] = '$'
M['B'] = '#'
M['c'] = '^'
M['d'] = '&'
M['1'] = '*'
M['2'] = '!'
M['E'] = '@'
# Function Call
generateLetters(S, 0, M);
# This code is contributed by _saurabh_jaiswal.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to generate all possible
// string by replacing the characters
// with mapped symbols
static void generateLetters(string S, int P,
Dictionary<char, char> M)
{
// Base Case
if (P == S.Length) {
Console.WriteLine(S);
return;
}
// Function call with the P-th
// character not replaced
generateLetters(S, P + 1, M);
// Replace the P-th character
S = S.Substring(0, P) + M[S[P]] + S.Substring(P + 1);
// Function call with the P-th
// character replaced
generateLetters(S, P + 1, M);
return;
}
// Driver Code
public static void Main()
{
string S = "aBc";
Dictionary<char, char> M = new Dictionary<char,char>();
M.Add('a','$');
M.Add('B','#');
M.Add('c','^');
M.Add('d','&');
M.Add('1','*');
M.Add('2','!');
M.Add('E','@');
// Function Call
generateLetters(S, 0, M);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to generate all possible
// string by replacing the characters
// with mapped symbols
function generateLetters(S, P, M)
{
// Base Case
if (P == S.length)
{
document.write(S + "<br>");
return;
}
// Function call with the P-th
// character not replaced
generateLetters(S, P + 1, M);
// Replace the P-th character
S = S.replace(S.charAt(P), M.get(S[P]))
// Function call with the P-th
// character replaced
generateLetters(S, P + 1, M);
return;
}
// Driver Code
let S = "aBc";
let M = new Map();
M.set('a', '$');
M.set('B', '#');
M.set('c', '^');
M.set('d', '&');
M.set('1', '*');
M.set('2', '!');
M.set('E', '@');
// Function Call
generateLetters(S, 0, M);
// This code is contributed by Potta Lokesh
</script>
Producción:
aBc aB^ a#c a#^ $Bc $B^ $#c $#^
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shawavisek35 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA