Kaikki merkkijonoyhdistelmät, joita voidaan käyttää numeron valitsemiseen
Annetaan numero tulosta kaikki mahdolliset yhdistelmät merkkijonoista, joita voidaan käyttää antamaan annettu numero puhelimessa seuraavilla eritelmillä. Annetussa puhelimessa voimme soittaa 2 käyttämällä a tai b tai c 3 käyttämällä d tai e tai f ................... 8 käyttämällä t tai u tai v 9 käyttämällä w tai x tai y tai z 1 käyttämällä vain 1 0 käyttämällä 0. Esimerkiksi jos 23 on annettu puhelinnumero, ohjelman tulisi tulostaa ad ae af bd be bf cd ce cf cf
Ajatuksena on tallentaa numero hahmoihin, jotka kartoittavat hash -kartassa. Kartta tallentaa kaikki merkit, joita voidaan käyttää, valitse numero. Asetamme kaikki mahdolliset hahmot nykyiseen numeroon ja toistamme jäljellä olevia numeroita.
Algoritmi:
- Luo avainten hash -kartta numerointina 0 - 9 ja arvot kunkin numeroon liittyvien merkkijoukkojen joukossa.
- Määritä rekursiivinen funktion tulostusstrings, joka ottaa neljä argumenttia:
a. Phno - Syöttöpuhelinnumero
b. I - Nykyisen numeron hakemisto
c. HM - Hash -digitalikartta merkkisarjoihin
d. Str - toistaiseksi luotu merkkijono - Tulostusprosenttien sisällä:
a. Tarkista, olenko saavuttanut puhelinnumeron lopun. Jos kyllä, tulosta luotu merkkijono ja palauta.
b. Hanki Hash -kartan nykyiseen numeroon liittyvä merkkijoukko.
c. Iteroi sarjan jokaisen merkin päälle ja:
i. Liitä merkki merkkijonoon.
II. Soita rekursiivisesti seuraavan numeron PrintStrings -toiminto.
III. Poista viimeinen merkki merkkijonosta. - Määritä funktio tulostuskorjaus, joka ottaa yhden argumentin:
a. Phno - Syöttöpuhelinnumero - PrintStringFornumber -toiminnon sisällä kutsu PrintStrings -toimintoa argumenteilla PHNO 0 HM ja tyhjä merkkijono.
Alla on tämän idean Java -toteutus.
Toteutus:
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' );
Tulos
AD AE AF BD BE BF CD CE CF
Ajan monimutkaisuus: O (2^n) Tässä n on merkkijonon pituus
Aputila: O (n)
