Všetky kombinácie reťazcov, ktoré sa dajú použiť na vytáčanie čísla
Vzhľadom na číslo vytlačte všetko možné kombinácia reťazcov, ktoré sa dajú použiť na vytáčanie daného čísla v telefóne s nasledujúcimi špecifikáciami. V danom telefóne môžeme vytáčať 2 pomocou A alebo B alebo C 3 pomocou D alebo E alebo F ................... 8 Používanie T alebo U alebo v 9 pomocou W alebo X alebo Y alebo z 1 pomocou iba 1 0. Napríklad, ak 23 je dané telefónne číslo, program by mal program vytlačiť
Zámerom je uložiť mapovanie číslic k znakom v mape hash. Mapa ukladá všetky znaky, ktoré je možné použiť, vytočte číslicu. Umiestnite všetky možné znaky pre aktuálnu číslicu a opakujú sa na zostávajúce číslice.
Algoritmus:
- Vytvorte hashovú mapu s klávesmi ako číslice od 0 do 9 a hodnoty ako množinu znakov spojených s každou číslicou.
- Definujte rekurzívne tlačové tlače, ktoré majú štyri argumenty:
a. PHNO - vstupné telefónne číslo
b. i - index spracovania aktuálnej číslice
c. HM - hashová mapa číslic do znakov
d. str - doteraz generovaný reťazec znakov - Vo vnútri funkcie PrintStrings:
a. Skontrolujte, či som dosiahol koniec telefónneho čísla. Ak áno vytlačte vygenerovaný reťazec a vráťte sa.
b. Získajte sadu znakov spojených s aktuálnou číslicou z mapy hash.
c. Iterovať nad každou postavou v sade a:
i. Pripojte znak k String Str.
II. Rekurzívne zavolajte funkciu PrintStrings pre ďalšiu číslicu.
III. Odstráňte posledný znak zo strunového struka. - Definujte funkciu PrintStringfornumber, ktorý má jeden argument:
a. PHNO - vstupné telefónne číslo - Vo vnútri funkcie PrintStringfornumber zavolajte funkciu PrintStrings funkciou s argumentmi PHNO 0 HM a prázdnym reťazcom.
Nižšie je implementácia tejto myšlienky Java.
Implementácia:
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' );
Výstup
AD AE AF BD BE BF CD CE CF
Časová zložitosť: o (2^n) tu n je dĺžka reťazca
Pomocný priestor: o (n)
