Дано число друкувати все можливе комбінації рядків, які можна використовувати для набору заданого номера в телефоні з наступними специфікаціями. У даному телефоні ми можемо набрати 2 за допомогою A або B або C 3 за допомогою D або E або F ................... 8 за допомогою T або U або V 9 за допомогою W або X або Y або Z 1, використовуючи лише 1 0, використовуючи 0.
Ідея полягає в тому, щоб зберігати цифру для персонажів, що відображають на хеш -карті. Карта зберігає всі символи, які можна використовувати набору цифри. Ми розміщуємо всіх можливих персонажів для поточної цифри та рецидиву для решти цифр.
java рядок масиву
Алгоритм:
- Створіть хеш -карту з клавішами як цифри від 0 до 9 та значення як набір символів, пов'язаних з кожною цифрою.
- Визначте рекурсивну функцію друку, яка займає чотири аргументи:
а. PHNO - номер телефону введення
б. i - індекс поточної цифри, що обробляється
c. HM - хеш -карта цифри до символів
д. str - рядок символів, що генеруються досі - Всередині функції PrintStrings:
а. Перевірте, чи я дійшов до кінця номера телефону. Якщо так, друкуйте створений рядок і повернути.
б. Отримайте набір символів, пов’язаних із поточною цифрою з хеш -карти.
c. Повторюйте кожного символу в наборі та:
я. Додавайте символ до рядка Str.
ii. Рекурсивно зателефонуйте функції PrintStrings для наступної цифри.
iii. Видаліть останній символ із рядка Str. - Визначте функцію printstringfornumber, який приймає один аргумент:
а. PHNO - номер телефону введення - Всередині функції PrintStringFornumber викликає функція PrintStrings за допомогою аргументів PHNO 0 HM та порожнім рядком.
Нижче наведено Java реалізацію цієї ідеї.
Реалізація:
C++// C++ program for the above approach #include
// 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'); } }
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')
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'); } }
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');
Випуск
AD AE AF BD BE BF CD CE CF
Складність часу: o (2^n) Тут n - довжина рядка
Допоміжний простір: o (n)
черга та пріоритетна черга в java