Dada una string de caracteres de longitud inferior a 10. Necesitamos imprimir todas las abreviaturas alfanuméricas de la string. La abreviatura alfanumérica tiene la forma de caracteres mezclados con los dígitos que es igual al número de caracteres omitidos de una substring seleccionada.
Por lo tanto, cada vez que se omite una substring de caracteres, debe reemplazarla con el dígito que indica el número de caracteres en la substring. Puede haber cualquier número de substrings omitidas de una string. No deben haber dos substrings adyacentes entre sí. Por lo tanto, no hay dos dígitos adyacentes en el resultado. Para una idea más clara, vea el ejemplo.
Ejemplos:
Input : ANKS Output : ANKS (nothing is replaced) ANK1 (S is replaced) AN1S (K is replaced) AN2 (KS is replaced) A1KS (N is replaced) A1K1 (N and S are replaced) A2S (NK is replaced) A3 (NKS is replaced) 1NKS (A is replaced) 1NK1 (A and S are replaced) 1N1S (A and N is replaced) 1N2 (A and KS are replaced) 2KS (AN is replaced) 2K1 (AN and S is replaced) 3S (ANK is replaced) 4 (ANKS is replaced) Input : ABC Output : ABC AB1 A1C A2 1BC 1B1 2C 3 Note: 11C is not valid because no two digits should be adjacent, 2C is the correct one because AB is a substring, not A and B individually
Fuente: pregunta de la entrevista de Google
La idea es comenzar con una string vacía. En cada paso, tenemos dos opciones.
- Considera el carácter tal como es.
- Añadir carácter para contar. Si no hay conteo, entonces use 1.
Puede ver cómo cada carácter puede sumarse al resultado como un carácter o como un dígito. Esto además da lugar a 2^n abreviaturas al final, donde n es la longitud de la string.
Implementación:
CPP
// C++ program to print all Alpha-Numeric Abbreviations
// of a String
#include <bits/stdc++.h>
using namespace std;
// Recursive function to print the valid combinations
// s is string, st is resultant string
void printCompRec(const string& s, int index,
int max_index, string st)
{
// if the end of the string is reached
if (index == max_index) {
cout << st << "\n";
return;
}
// push the current character to result
st.push_back(s[index]);
// recur for the next [Using Char]
printCompRec(s, index + 1, max_index, st);
// remove the character from result
st.pop_back();
// set count of digits to 1
int count = 1;
// addition the adjacent digits
if (!st.empty()) {
if (isdigit(st.back())) {
// get the digit and increase the count
count += (int)(st.back() - '0');
// remove the adjacent digit
st.pop_back();
}
}
// change count to a character
char to_print = (char)(count + '0');
// add the character to result
st.push_back(to_print);
// recur for this again [Using Count]
printCompRec(s, index + 1, max_index, st);
}
// Wrapper function
void printComb(std::string s)
{
// if the string is empty
if (!s.length())
return;
// Stores result strings one by one
string st;
printCompRec(s, 0, s.length(), st);
}
// driver function
int main()
{
string str = "GFG";
printComb(str);
return 0;
}
Python3
# Python program to print all Alpha-Numeric Abbreviations
# of a String
# Recursive function to print the valid combinations
# s is string, st is resultant string
def printCompRec(s, index, max_index, st):
# if the end of the string is reached
if (index == max_index):
print(st)
return
# push the current character to result
st += s[index]
# recur for the next [Using Char]
printCompRec(s, index + 1, max_index, st)
# remove the character from result
st = st[0:len(st)-1]
# set count of digits to 1
count = 1
# addition the adjacent digits
if (len(st) > 0):
if (ord(st[-1])>=ord('0') and ord(st[-1])<=ord('9')):
# get the digit and increase the count
count += (ord(st[-1]) - ord('0'))
# remove the adjacent digit
st = st[0:len(st)-1]
# change count to a character
to_print = chr(count + ord('0'))
# add the character to result
st += to_print
# recur for this again [Using Count]
printCompRec(s, index + 1, max_index, st)
# Wrapper function
def printComb(s):
# if the string is empty
if (len(s) == 0):
return
# Stores result strings one by one
st = ""
printCompRec(s, 0, len(s), st)
# driver function
Str = "GFG"
printComb(Str)
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to print all Alpha-Numeric Abbreviations
// of a String
// Recursive function to print the valid combinations
// s is string, st is resultant string
function printCompRec(s, index, max_index, st){
// if the end of the string is reached
if (index == max_index){
document.write(st,"</br>")
return
}
// push the current character to result
st += s[index]
// recur for the next [Using Char]
printCompRec(s, index + 1, max_index, st)
// remove the character from result
st = st.substring(0,st.length-1)
// set count of digits to 1
let count = 1
// addition the adjacent digits
if (st.length > 0){
if (st.charCodeAt(st.length-1)>='0'.charCodeAt(0) && st.charCodeAt(st.length-1)<='9'.charCodeAt(0)){
// get the digit and increase the count
count += (st.charCodeAt(st.length-1) - '0'.charCodeAt(0))
// remove the adjacent digit
st = st.substring(0,st.length-1)
}
}
// change count to a character
let to_print = String.fromCharCode(count + '0'.charCodeAt(0))
// add the character to result
st += to_print
// recur for this again [Using Count]
printCompRec(s, index + 1, max_index, st)
}
// Wrapper function
function printComb(s){
// if the string is empty
if (s.length == 0)
return
// Stores result strings one by one
let st = ""
printCompRec(s, 0, s.length, st)
}
// driver function
let Str = "GFG"
printComb(Str)
// This code is contributed by shinjanpatra
</script>
GFG GF1 G1G G2 1FG 1F1 2G 3
Podemos generar todas estas abreviaturas iterativamente también
Algoritmo:
1. Deje que la string de longitud n = 3, str = valor binario «ABC»
entre 0 y 7 ayudará a decidir qué carácter se usará o qué carácter se reemplazará
Si, por ejemplo, n = 6, binario = 110
considere cada posición de bit binario como bit de índice
= 1 significa que será reemplazado y 0 significa que no estamos cambiando ese carácter de índice y 0 significa que permanecerá como está
Implementación:
Java
import java.io.*;
import java.util.*;
public class Main {
private static void printans(String str)
{
String ans = "";
int counter = 0;
for (char ch : str.toCharArray()) {
if (ch == '-') {
counter++;
}
else {
if (counter > 0)
ans = ans + counter;
counter = 0;
ans = ans + ch;
}
}
if (counter > 0)
ans = ans + counter;
System.out.println(ans);
}
public static void main(String[] args)
{
String str = "ANKS";
int n = str.length();
int limit = 1 << n;
for (int i = 0; i < limit; i++) {
int counter = i, idx = 0;
String abb = "";
for (int b = 0; b < n; b++) {
int bit = counter % 2;
counter /= 2;
if (bit == 1) {
abb = abb + "-";
}
else {
abb = abb + str.charAt(idx);
}
idx++;
}
printans(abb);
}
}
}
ANKS 1NKS A1KS 2KS AN1S 1N1S A2S 3S ANK1 1NK1 A1K1 2K1 AN2 1N2 A3 4
Este artículo es una contribución de Aditya Nihal Kumar Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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