Dada la string numérica str , donde 1 representa ‘a’ , 2 representa ‘b’ , …, 26 representa ‘z’ , la tarea es imprimir todas las strings alfabéticas posibles que se pueden obtener de str .
Ejemplos:
Entrada: str = “1123”
Salida:
aabc
kbc
alc
aaw
kw
Explicación:
La string dada se puede dividir como:
1) “1123” = “1” + “1” + “2” + “3” = aabc
2) “ 1123” = “11” + “2” + “3” = kbc
3) “1123” = “1” + “12” + “3” = alc
4) “1123” = “1” + “1” + “ 23” = aaw
5) “1123” = “11” + “23” = aabcEntrada: str = “56”
Salida:
ef
Explicación:
La string dada se puede dividir como:
1) “56” = “5” + “6” = ef
Planteamiento : Se puede observar que cada carácter individual representa un alfabeto excepto el 0 . Este problema es recursivo y se puede dividir en subproblemas. La condición de terminación será cuando la string pasada esté vacía. A continuación se muestran los pasos para resolver el problema:
- Cree una función auxiliar getChar() que devuelva el alfabeto correspondiente del carácter numérico dado.
- Cree una función recursiva que tome la entrada como una string y devuelva una array de la respuesta deseada de cada carácter extraído.
- El caso base es cuando la string de entrada está vacía . Devuelve una array de longitud uno que contiene una string vacía para este caso.
- Extraiga cada carácter usando la función de ayuda y agréguelo primero a la string vacía y guárdelo en una array, digamos output1 .
- Al mismo tiempo, verifique si la longitud de los caracteres es mayor o igual a dos y también verifique si los dos caracteres extraídos se encuentran en el rango de los alfabetos. Ahora, almacene el carácter correspondiente en una array, digamos output2 .
- Luego, cree una array de salida final cuya longitud será la suma de la longitud de salida1 y salida2 , almacene sus respuestas y devuélvalas.
- Repita los pasos anteriores para cada uno o cada par de caracteres adyacentes extraídos. Ahora, devuelva la array final obtenida.
- Recorra la array y para cada string, genere las strings correspondientes de alfabetos en minúsculas e imprímalas.
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 check if all the
// characters are lowercase or not
bool nonLower(string s)
{
// Traverse the string
for(int i = 0; i < s.size(); i++)
{
// If any character is not
// found to be in lowerCase
if (!islower(s[i]))
{
return true;
}
}
return false;
}
// Function to print the decodings
void printCodes(vector<string> output)
{
for(int i = 0; i < output.size(); i++)
{
// If all characters are not
// in lowercase
if (nonLower(output[i]))
continue;
cout << (output[i]) << endl;
}
}
// Function to return the character
// corresponding to given integer
char getChar(int n)
{
return (char)(n + 96);
}
// Function to return the decodings
vector<string> getCode(string str)
{
// Base case
if (str.size() == 0)
{
vector<string> ans;
ans.push_back("");
return ans;
}
// Recursive call
vector<string> output1 = getCode(str.substr(1));
// Stores the characters of
// two digit numbers
vector<string> output2(0);
// Extract first digit and
// first two digits
int firstDigit= (str[0] - '0');
int firstTwoDigit = 0;
if (str.size() >= 2)
{
firstTwoDigit = (str[0] - '0') * 10 +
(str[1] - '0');
// Check if it lies in the
// range of alphabets
if (firstTwoDigit >= 10 &&
firstTwoDigit <= 26)
{
// Next recursive call
output2 = getCode(str.substr(2));
}
}
// Combine both the output in a
// single final output array
vector<string> output(output1.size() +
output2.size());
// Index of final output array
int k = 0;
// Store the elements of output1
// in final output array
for(int i = 0; i < output1.size(); i++)
{
char ch = getChar(firstDigit);
output[i] = ch + output1[i];
k++;
}
// Store the elements of output2
// in final output array
for(int i = 0; i < output2.size(); i++)
{
char ch = getChar(firstTwoDigit);
output[k] = ch + output2[i];
k++;
}
// Result the result
return output;
}
// Driver Code
int main()
{
string input = "101";
// Function call
vector<string> output = getCode(input);
// Print function call
printCodes(output);
}
// This code is contributed by grand_master
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to check if all the
// characters are lowercase or not
public static boolean
nonLower(String s)
{
// Traverse the string
for (int i = 0; i < s.length(); i++) {
// If any character is not
// found to be in lowerCase
if (!Character
.isLowerCase(s.charAt(i))) {
return true;
}
}
return false;
}
// Function to print the decodings
public static void
printCodes(String output[])
{
for (int i = 0; i < output.length; i++) {
// If all characters are not
// in lowercase
if (nonLower(output[i]))
continue;
System.out.println(output[i]);
}
}
// Function to return the character
// corresponding to given integer
public static char getChar(int n)
{
return (char)(n + 96);
}
// Function to return the decodings
public static String[] getCode(
String str)
{
// Base case
if (str.length() == 0) {
String ans[] = { "" };
return ans;
}
// Recursive call
String output1[]
= getCode(str.substring(1));
// Stores the characters of
// two digit numbers
String output2[] = new String[0];
// Extract first digit and
// first two digits
int firstDigit
= (str.charAt(0) - '0');
int firstTwoDigit = 0;
if (str.length() >= 2) {
firstTwoDigit
= (str.charAt(0) - '0') * 10
+ (str.charAt(1) - '0');
// Check if it lies in the
// range of alphabets
if (firstTwoDigit >= 10
&& firstTwoDigit <= 26) {
// Next recursive call
output2
= getCode(str.substring(2));
}
}
// Combine both the output in a
// single final output array
String output[]
= new String[output1.length
+ output2.length];
// Index of final output array
int k = 0;
// Store the elements of output1
// in final output array
for (int i = 0; i < output1.length; i++) {
char ch = getChar(firstDigit);
output[i] = ch + output1[i];
k++;
}
// Store the elements of output2
// in final output array
for (int i = 0; i < output2.length; i++) {
char ch = getChar(firstTwoDigit);
output[k] = ch + output2[i];
k++;
}
// Result the result
return output;
}
// Driver Code
public static void main(String[] args)
{
String input = "101";
// Function call
String output[] = getCode(input);
// Print function call
printCodes(output);
}
}
Python3
# Python3 program for
# the above approach
# Function to check if all the
# characters are lowercase or not
def nonLower(s):
# Traverse the string
for i in range(len(s)):
# If any character is not
# found to be in lowerCase
if not s[i].islower():
return True
return False
# Function to print the decodings
def printCodes(output):
for i in range(len(output)):
# If all characters are not
# in lowercase
if (nonLower(output[i])):
continue
print(output[i])
# Function to return the character
# corresponding to given integer
def getChar(n):
return chr(n + 96)
# Function to return the decodings
def getCode(str):
# Base case
if (len(str) == 0):
ans = [""]
return ans
# Recursive call
output1 = getCode(str[1:])
# Stores the characters of
# two digit numbers
output2 = []
# Extract first digit and
# first two digits
firstDigit = (ord(str[0]) - ord('0'))
firstTwoDigit = 0
if (len(str) >= 2):
firstTwoDigit = ((ord(str[0]) - ord('0')) * 10 +
(ord(str[1]) - ord('0')))
# Check if it lies in the
# range of alphabets
if (firstTwoDigit >= 10 and firstTwoDigit <= 26):
# Next recursive call
output2 = getCode(str[2:])
# Combine both the output in a
# single readonly output array
output = ['' for i in range(len(output1) +
len(output2))]
# Index of readonly output array
k = 0
# Store the elements of output1
# in readonly output array
for i in range(len(output1)):
ch = getChar(firstDigit)
output[i] = ch + output1[i]
k += 1
# Store the elements of output2
# in readonly output array
for i in range(len(output2)):
ch = getChar(firstTwoDigit)
output[k] = ch + output2[i]
k += 1
# Result the result
return output
# Driver Code
if __name__=='__main__':
input = "101"
# Function call
output = getCode(input)
# Print function call
printCodes(output)
# This code is contributed by rutvik_56
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to check if all the
// characters are lowercase or not
public static bool nonLower(String s)
{
// Traverse the string
for (int i = 0; i < s.Length; i++)
{
// If any character is not
// found to be in lowerCase
if (!char.IsLower(s[i]))
{
return true;
}
}
return false;
}
// Function to print the decodings
public static void printCodes(String []output)
{
for (int i = 0; i < output.Length; i++)
{
// If all characters are not
// in lowercase
if (nonLower(output[i]))
continue;
Console.WriteLine(output[i]);
}
}
// Function to return the character
// corresponding to given integer
public static char getChar(int n)
{
return (char)(n + 96);
}
// Function to return the decodings
public static String[] getCode(String str)
{
// Base case
if (str.Length == 0)
{
String []ans = { "" };
return ans;
}
// Recursive call
String []output1 = getCode(str.Substring(1));
// Stores the characters of
// two digit numbers
String []output2 = new String[0];
// Extract first digit and
// first two digits
int firstDigit = (str[0] - '0');
int firstTwoDigit = 0;
if (str.Length >= 2)
{
firstTwoDigit = (str[0] - '0') * 10 +
(str[1] - '0');
// Check if it lies in the
// range of alphabets
if (firstTwoDigit >= 10 &&
firstTwoDigit <= 26)
{
// Next recursive call
output2 = getCode(str.Substring(2));
}
}
// Combine both the output in a
// single readonly output array
String []output = new String[output1.Length +
output2.Length];
// Index of readonly output array
int k = 0;
// Store the elements of output1
// in readonly output array
for (int i = 0; i < output1.Length; i++)
{
char ch = getChar(firstDigit);
output[i] = ch + output1[i];
k++;
}
// Store the elements of output2
// in readonly output array
for (int i = 0; i < output2.Length; i++)
{
char ch = getChar(firstTwoDigit);
output[k] = ch + output2[i];
k++;
}
// Result the result
return output;
}
// Driver Code
public static void Main(String[] args)
{
String input = "101";
// Function call
String []output = getCode(input);
// Print function call
printCodes(output);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function to check if all the
// characters are lowercase or not
function nonLower(s)
{
// Traverse the string
for(let i = 0; i < s.length; i++)
{
// If any character is not
// found to be in lowerCase
if (!(s[i].charCodeAt() >= 97 && s[i].charCodeAt() <= 122))
{
return true;
}
}
return false;
}
// Function to print the decodings
function printCodes(output)
{
for (let i = 0; i < output.length; i++)
{
// If all characters are not
// in lowercase
if (nonLower(output[i]))
continue;
document.write(output[i] + "</br>");
}
}
// Function to return the character
// corresponding to given integer
function getChar(n)
{
return String.fromCharCode(n + 96);
}
// Function to return the decodings
function getCode(str)
{
// Base case
if (str.length == 0)
{
let ans = [ "" ];
return ans;
}
// Recursive call
let output1 = getCode(str.substring(1));
// Stores the characters of
// two digit numbers
let output2 = new Array(0);
// Extract first digit and
// first two digits
let firstDigit = (str[0] - '0');
let firstTwoDigit = 0;
if (str.length >= 2)
{
firstTwoDigit = (str[0].charCodeAt() - '0'.charCodeAt()) * 10 +
(str[1].charCodeAt() - '0'.charCodeAt());
// Check if it lies in the
// range of alphabets
if (firstTwoDigit >= 10 &&
firstTwoDigit <= 26)
{
// Next recursive call
output2 = getCode(str.substring(2));
}
}
// Combine both the output in a
// single readonly output array
let output = new Array(output1.length + output2.length);
// Index of readonly output array
let k = 0;
// Store the elements of output1
// in readonly output array
for (let i = 0; i < output1.length; i++)
{
let ch = getChar(firstDigit);
output[i] = ch + output1[i];
k++;
}
// Store the elements of output2
// in readonly output array
for (let i = 0; i < output2.length; i++)
{
let ch = getChar(firstTwoDigit);
output[k] = ch + output2[i];
k++;
}
// Result the result
return output;
}
let input = "101";
// Function call
let output = getCode(input);
// Print function call
printCodes(output);
// This code is contributed by mukesh07.
</script>
Producción:
ja
Complejidad de tiempo: O(2 N )
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por piyushnayan062 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA