Todas as combinações de cordas que podem ser usadas para discar um número
Dado um número imprimido tudo possível Combinações de strings que podem ser usadas para discar o número fornecido em um telefone com as seguintes especificações. No telefone fornecido, podemos discar 2 usando A ou B ou C 3 usando D ou E ou F ................... 8 Usando T ou U ou V 9 usando W ou X ou Y ou Z 1 usando apenas 1 0 usando 0. Por exemplo, se 23 é o número de telefone fornecido, o programa deve imprimir anúncios AE AF BD BF CD CF CF CF
A idéia é armazenar dígitos para mapear os caracteres no mapa de hash. O mapa armazena todos os caracteres que podem ser usados discar um dígito. Colocamos todos os personagens possíveis para o dígito atual e recorremos para os dígitos restantes.
Algoritmo:
- Crie um mapa de hash com teclas como dígitos de 0 a 9 e valores como o conjunto de caracteres associados a cada dígito.
- Defina uma estampa de função recursiva que leva quatro argumentos:
um. PhnO - o número de telefone de entrada
b. i - o índice do dígito atual sendo processado
c. HM - o mapa de hash do dígito para conjuntos de caracteres
d. STR - A sequência de caracteres gerados até agora - Dentro da função PrintStrings:
um. Verifique se eu atingi o final do número de telefone. Se sim, imprima a string gerada e retorne.
b. Obtenha o conjunto de caracteres associados ao dígito atual do mapa de hash.
c. Itera sobre cada personagem no conjunto e:
eu. Anexe o personagem ao String str.
ii. Chame recursivamente a função PrintStrings para o próximo dígito.
iii. Remova o último caractere do String str. - Defina uma função PrintStringFornumber que requer um argumento:
um. PhnO - o número de telefone de entrada - Dentro da função PrintStringForNumber, ligue para a função PrintStrings com os argumentos phno 0 hm e uma string vazia.
Abaixo está a implementação de Java dessa ideia.
Implementação:
C++ // C++ program for the above approach #include #include using namespace std ; void printStrings ( string phNo int i unordered_map < char string > hm string str ) { if ( i == phNo . length ()) { cout < < str < < ' ' ; return ; } string s = hm [ phNo [ i ]]; for ( int j = 0 ; j < s . length (); j ++ ) { str . push_back ( s [ j ]); printStrings ( phNo i + 1 hm str ); str . pop_back (); } } void printStringForNumber ( string phNo ) { unordered_map < char string > hm = { { '2' 'ABC' } { '3' 'DEF' } { '4' 'GHI' } { '5' 'JKL' } { '6' 'MNO' } { '7' 'PQRS' } { '8' 'TUV' } { '9' 'WXYZ' } { '1' '1' } { '0' '0' } }; string str ; printStrings ( phNo 0 hm str ); } int main () { printStringForNumber ( '23' ); return 0 ; } // This code is contributed by codebraxnzt
Java // Java program to print all possible key strings // that can be used to dial a phone number. import java.util.HashMap ; class ConvertToString { // A Recursive function to print all combinations // that can be used to dial a given number. // phNo ==> Given Phone Number // i ==> Current digit of phNo to be processed // hm ==> Stores characters that can be used to // to dial a digit. // str ==> Current output string static void printStrings ( String phNo int i HashMap < Character String > hm StringBuilder str ) { // If all digits are processed print output // string if ( i == phNo . length ()) { System . out . print ( str + ' ' ); return ; } // Get current digit of phNo and recur for all // characters that can be used to dial it. String s = hm . get ( phNo . charAt ( i )); for ( int j = 0 ; j < s . length (); j ++ ) { str . append ( s . charAt ( j )); printStrings ( phNo i + 1 hm str ); str . deleteCharAt ( str . length () - 1 ); } } // Prints all possible combinations of strings that // can be used to dial c[]. static void printStringForNumber ( String phNo ) { // Create a HashMap HashMap < Character String > hm = new HashMap < Character String > (); // For every digit store characters that can // be used to dial it. hm . put ( '2' 'ABC' ); hm . put ( '3' 'DEF' ); hm . put ( '4' 'GHI' ); hm . put ( '5' 'JKL' ); hm . put ( '6' 'MNO' ); hm . put ( '7' 'PQRS' ); hm . put ( '8' 'TUV' ); hm . put ( '9' 'WXYZ' ); hm . put ( '1' '1' ); hm . put ( '0' '0' ); // Create a string to store a particular output // string StringBuilder str = new StringBuilder (); // Call recursive function printStrings ( phNo 0 hm str ); } // Driver code to test above methods public static void main ( String args [] ) { // Prints printStringForNumber ( '23' ); } }
Python def print_strings ( ph_no i hm s ): if i == len ( ph_no ): print ( s end = ' ' ) return for c in hm [ ph_no [ i ]]: print_strings ( ph_no i + 1 hm s + c ) def print_string_for_number ( ph_no ): hm = { '2' : 'ABC' '3' : 'DEF' '4' : 'GHI' '5' : 'JKL' '6' : 'MNO' '7' : 'PQRS' '8' : 'TUV' '9' : 'WXYZ' '1' : '1' '0' : '0' } s = '' print_strings ( ph_no 0 hm s ) print_string_for_number ( '23' )
C# using System ; using System.Collections.Generic ; class Program { static void printStrings ( string phNo int i Dictionary < char string > hm string str ) { if ( i == phNo . Length ) { Console . Write ( str + ' ' ); return ; } string s = hm [ phNo [ i ]]; for ( int j = 0 ; j < s . Length ; j ++ ) { str += s [ j ]; printStrings ( phNo i + 1 hm str ); str = str . Remove ( str . Length - 1 ); } } static void printStringForNumber ( string phNo ) { Dictionary < char string > hm = new Dictionary < char string > { { '2' 'ABC' } { '3' 'DEF' } { '4' 'GHI' } { '5' 'JKL' } { '6' 'MNO' } { '7' 'PQRS' } { '8' 'TUV' } { '9' 'WXYZ' } { '1' '1' } { '0' '0' } }; string str = '' ; printStrings ( phNo 0 hm str ); } static void Main ( string [] args ) { printStringForNumber ( '23' ); } }
JavaScript function printStrings ( phNo i hm s ) { if ( i === phNo . length ) { console . log ( s + ' ' ); return ; } for ( let j = 0 ; j < hm [ phNo [ i ]]. length ; j ++ ) { s += hm [ phNo [ i ]][ j ]; printStrings ( phNo i + 1 hm s ); s = s . slice ( 0 - 1 ); } } function printStringForNumber ( phNo ) { let hm = { '2' : 'ABC' '3' : 'DEF' '4' : 'GHI' '5' : 'JKL' '6' : 'MNO' '7' : 'PQRS' '8' : 'TUV' '9' : 'WXYZ' '1' : '1' '0' : '0' }; let s = '' ; printStrings ( phNo 0 hm s ); } printStringForNumber ( '23' );
Saída
AD AE AF BD BE BF CD CE CF
Complexidade do tempo: o (2^n) Aqui n é o comprimento da corda
Espaço auxiliar: O (n)
