Wszystkie kombinacje ciągów, które można użyć do wybierania numeru
Biorąc pod uwagę, że druk numer wszystko możliwe kombinacje ciągów, które można użyć do wybierania podanego numeru w telefonie z następującymi specyfikacjami. W danym telefonie możemy wybrać 2 za pomocą a lub b lub c 3 za pomocą d lub e lub f ................... 8 za pomocą t lub u lub v 9 za pomocą w lub x lub z 1 za pomocą tylko 1 0 za pomocą 0. Na przykład, jeśli 23 jest podanym numerem telefonu, program powinien wydrukować reklam
Chodzi o to, aby przechowywać cyfrę do mapowania znaków na mapie skrótu. Mapa przechowuje wszystkie znaki, których można użyć, wybierz cyfrę. Umieszczamy każdy możliwy znak prądu cyfry i powtarzamy się dla pozostałych cyfr.
Algorytm:
- Utwórz mapę skrótu z klawiszami jako cyfry od 0 do 9 i wartościami jako zestaw znaków powiązanych z każdą cyfrą.
- Zdefiniuj przedłużenie funkcji rekurencyjnej, która przyjmuje cztery argumenty:
A. PHNO - numer telefonu wejściowego
B. I - Indeks bieżącej cyfry przetwarzanej
C. HM - mapa skrótu cyfr do zestawów znaków
D. Str - ciąg wygenerowanych do tej pory znaków znaków - Wewnątrz funkcji PrintStrings:
A. Sprawdź, czy osiągnąłem koniec numeru telefonu. Jeśli tak, wydrukuj generowany ciąg i zwróć.
B. Uzyskaj zestaw znaków powiązanych z bieżącą cyfrą z mapy skrótu.
C. Iteruj nad każdą postacią w planie i:
I. Dodaj znak do String Str.
ii. Rekurencyjnie wywołuje funkcję PrintStrings dla następnej cyfry.
iii. Usuń ostatni znak z łańcucha str. - Zdefiniuj funkcję PrintStringFornumber, która przyjmuje jeden argument:
A. PHNO - numer telefonu wejściowego - Wewnątrz funkcji PrintStringFornumber wywołaj funkcję PrintStrings z argumentami Phno 0 Hm i pustym ciągiem.
Poniżej jest wdrożenie tego pomysłu w Javie.
Realizacja:
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' );
Wyjście
AD AE AF BD BE BF CD CE CF
Złożoność czasu: o (2^n) tutaj n ma długość ciągu
Przestrzeń pomocnicza: o (n)
