با توجه به یک صفحه کلید همانطور که در نمودار نشان داده شده است، و یک عدد رقمی n ، تمام کلماتی را که با فشار دادن این اعداد ممکن است فهرست کنید.
قبل از ظهور صفحه کلید QWERTY، متون و اعداد روی یک کلید قرار می گرفتند. به عنوان مثال، 2 دارای "ABC" است، بنابراین اگر میخواهیم چیزی بنویسیم که با A شروع میشود، باید یک بار کلید 2 را تایپ کنیم. اگر میخواهیم "B" را تایپ کنیم، کلید 2 را دو بار و سه بار برای تایپ "C" فشار دهید. در زیر تصویری از چنین صفحه کلیدی را مشاهده می کنید.
مثال ها:
ورودی: 234
خروجی: adg adh adi aeg aeh aei afg afh
afi bdg bdh bdi beg beh bei bfg
bfh bfi cdg cdg cd cdi ceg ceh ceh cei
cfg cfh cfiتوضیح: تمام کلمات ممکنی که می توانند
تشکیل شوند عبارتند از (به ترتیب حروف الفبا):
adg adh adi aeg aeh aei afg afh
afi bdg bdh bdi beg beh bei bfg
bfh bfi cdg cdh cdi ceg ceh cei
cfg cfh cfi
اگر 2 فشار داده شود، الفبا می تواند a، b، c،
به طور مشابه، برای 3، می تواند d، e، f، و برای 4 می تواند g، h، i باشد.ورودی: 5
خروجی: jkl
توضیح: تمام کلمات ممکنی که می توان
تشکیل داد (به ترتیب حروف الفبا):
j، k، l، فقط این سه الفبا را
می توان با j، k، l نوشت.
رویکرد: برای حل مشکل ایده زیر را دنبال کنید:
می توان مشاهده کرد که هر رقم می تواند 3 تا 4 الفبای مختلف (به غیر از 0 و 1) را نشان دهد. بنابراین ایده این است که یک تابع بازگشتی را تشکیل دهیم. سپس عدد را با رشته الفبای احتمالی خود ترسیم کنید، یعنی 2 با "abc"، 3 با "def" و غیره. اکنون تابع بازگشتی تمام حروف الفبا را که به ترتیب حروف الفبا به رقم فعلی نگاشت شده است امتحان می کند و دوباره تابع بازگشتی را فراخوانی می کند. برای رقم بعدی و به رشته خروجی فعلی منتقل می کند.
تصویر: اگر عدد 23 باشد،
- سپس برای 2، الفبای a، b، c هستند، بنابراین 3 تابع بازگشتی با رشته خروجی به ترتیب a، b، c و برای 3 3 الفبای d، e، f وجود دارد.
- بنابراین، خروجی ad، ae و af برای تابع بازگشتی با رشته خروجی خواهد بود.
- به طور مشابه، برای b و c، خروجی به ترتیب عبارتند از: bd، be، bf و cd، ce، cf.
الگوریتم: برای حل مشکل مراحل زیر را دنبال کنید:
- عدد را با رشته الفبای احتمالی خود ترسیم کنید، یعنی 2 با "abc"، 3 با "def" و غیره.
- یک تابع بازگشتی ایجاد کنید که پارامترهای زیر، رشته خروجی، آرایه اعداد، شاخص جاری و طول آرایه اعداد زیر را بگیرد.
- اگر شاخص فعلی برابر با طول آرایه اعداد باشد، رشته خروجی را چاپ کنید.
- رشته را در رقم[current_index] از نقشه استخراج کنید، جایی که رقم آرایه اعداد ورودی است.
- یک حلقه را اجرا کنید تا رشته را از ابتدا تا انتها طی کنید
- برای هر شاخص مجدداً تابع بازگشتی را با رشته خروجی الحاق با کاراکتر ith رشته و current_index + 1 فراخوانی کنید.
در زیر اجرای رویکرد فوق را مشاهده می کنید:
- C++
- سی
- جاوا
- پایتون 3
- سی شارپ
- جاوا اسکریپت
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find all possible combinations by
// replacing key's digits with characters of the
// corresponding list
void findCombinations(vector<char> keypad[], int input[],
string res, int index, int n)
{
// If processed every digit of key, print result
if (index == n) {
cout << res << " ";
return;
}
// Stores current digit
int digit = input[index];
// Size of the list corresponding to current digit
int len = keypad[digit].size();
// One by one replace the digit with each character in
// the corresponding list and recur for next digit
for (int i = 0; i < len; i++) {
findCombinations(keypad, input,
res + keypad[digit][i], index + 1,
n);
}
}
// Driver Code
int main()
{
// Given mobile keypad
vector<char> keypad[]
= { {},
{}, // 0 and 1 digit don't have any characters
// associated
{ 'a', 'b', 'c' },
{ 'd', 'e', 'f' },
{ 'g', 'h', 'i' },
{ 'j', 'k', 'l' },
{ 'm', 'n', 'o' },
{ 'p', 'q', 'r', 's' },
{ 't', 'u', 'v' },
{ 'w', 'x', 'y', 'z' } };
// Given input array
int input[] = { 2, 3, 4 };
// Size of the array
int n = sizeof(input) / sizeof(input[0]);
// Function call
findCombinations(keypad, input, string(""), 0, n);
return 0;
}
|
C
// C program for the above approach
#include <stdio.h>
#include <string.h>
// hashTable[i] stores all characters that correspond to
// digit i in phone
const char hashTable[10][5]
= { "", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz" };
// A recursive function to print all possible words that can
// be obtained by input number[] of size n. The output
// words are one by one stored in output[]
void printWordsUtil(int number[], int curr_digit,
char output[], int n)
{
// Base case, if current output word is prepared
int i;
if (curr_digit == n) {
printf("%s ", output);
return;
}
// Try all 3 possible characters for current digit in
// number[] and recur for remaining digits
for (i = 0; i < strlen(hashTable[number[curr_digit]]);
i++) {
output[curr_digit]
= hashTable[number[curr_digit]][i];
printWordsUtil(number, curr_digit + 1, output, n);
if (number[curr_digit] == 0
|| number[curr_digit] == 1)
return;
}
}
// A wrapper over printWordsUtil(). It creates an output
// array and calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n + 1];
result[n] = '\0';
printWordsUtil(number, 0, result, n);
}
// Driver code
int main(void)
{
int number[] = { 2, 3, 4 };
int n = sizeof(number) / sizeof(number[0]);
// Function call
printWords(number, n);
return 0;
}
|
Java
// Java program to implement the
// above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class NumberPadString {
static Character[][] numberToCharMap;
private static List<String> printWords(int[] numbers,
int len,
int numIndex,
String s)
{
if (len == numIndex) {
return new ArrayList<>(
Collections.singleton(s));
}
List<String> stringList = new ArrayList<>();
for (int i = 0;
i < numberToCharMap[numbers[numIndex]].length;
i++) {
String sCopy
= String.copyValueOf(s.toCharArray());
sCopy = sCopy.concat(
numberToCharMap[numbers[numIndex]][i]
.toString());
stringList.addAll(printWords(
numbers, len, numIndex + 1, sCopy));
}
return stringList;
}
private static void printWords(int[] numbers)
{
generateNumberToCharMap();
List<String> stringList
= printWords(numbers, numbers.length, 0, "");
stringList.stream().forEach(System.out::println);
}
private static void generateNumberToCharMap()
{
numberToCharMap = new Character[10][5];
numberToCharMap[0] = new Character[] { '\0' };
numberToCharMap[1] = new Character[] { '\0' };
numberToCharMap[2]
= new Character[] { 'a', 'b', 'c' };
numberToCharMap[3]
= new Character[] { 'd', 'e', 'f' };
numberToCharMap[4]
= new Character[] { 'g', 'h', 'i' };
numberToCharMap[5]
= new Character[] { 'j', 'k', 'l' };
numberToCharMap[6]
= new Character[] { 'm', 'n', 'o' };
numberToCharMap[7]
= new Character[] { 'p', 'q', 'r', 's' };
numberToCharMap[8]
= new Character[] { 't', 'u', 'v' };
numberToCharMap[9]
= new Character[] { 'w', 'x', 'y', 'z' };
}
// Driver code
public static void main(String[] args)
{
int number[] = { 2, 3, 4 };
// Function call
printWords(number);
}
}
// This code is contributed by ankit pachori 1
|
Python3
# Python3 program for the above approach
# hashTable[i] stores all characters
# that correspond to digit i in phone
hashTable = ["", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"]
# A recursive function to print all
# possible words that can be obtained
# by input number[] of size n. The
# output words are one by one stored
# in output[]
def printWordsUtil(number, curr, output, n):
if(curr == n):
print(output)
return
# Try all 3 possible characters
# for current digit in number[]
# and recur for remaining digits
for i in range(len(hashTable[number[curr]])):
output.append(hashTable[number[curr]][i])
printWordsUtil(number, curr + 1, output, n)
output.pop()
if(number[curr] == 0 or number[curr] == 1):
return
# A wrapper over printWordsUtil().
# It creates an output array and
# calls printWordsUtil()
def printWords(number, n):
printWordsUtil(number, 0, [], n)
# Driver function
if __name__ == '__main__':
number = [2, 3, 4]
n = len(number)
# Function call
printWords(number, n)
# This code is contributed by prajmsidc
|
C#
using System;
/*
C# Program for
Print all possible words from phone digits
*/
public class GFG {
// Function to find all possible combinations by
// replacing key's digits with characters of the
// corresponding list
static void findCombinations(String[] keypad,
int[] input, String result,
int index, int n)
{
// If processed every digit of key, print result
if (index == n) {
Console.Write(result + "\t");
return;
}
// Stores current digit
int digit = input[index];
// Size of the list corresponding to current digit
int len = keypad[digit].Length;
// One by one replace the digit with each character
// in the corresponding list and recur for next
// digit
for (int i = 0; i < len; i++) {
findCombinations(keypad, input,
result + keypad[digit][i],
index + 1, n);
}
}
public static void Main(String[] args)
{
// Keypad word of number of (1 to 9)
// 0 and 1 digit don't have any characters
// associated
String[] keypad
= { "", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz" };
String result = "";
// Given input array
int[] input = { 2, 3, 4 };
// Size of the array
int n = input.Length;
// Function call to find all combinations
findCombinations(keypad, input, result, 0, n);
}
}
// This code is contributed by Aarti_Rathi
|
Javascript
<script>
// Javascript program to implement the
// above approach
let hashTable = [ "", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz" ];
// A recursive function to print all possible
// words that can be obtained by input number[]
// of size n. The output words are one by one
// stored in output[]
function printWordsUtil(number, curr, output, n)
{
// Base case, if current output
// word is prepared
if (curr == n)
{
document.write(output.join("") + "<br>")
return;
}
// Try all 3 possible characters for current
// digit in number[] and recur for remaining digits
for(let i = 0;
i < hashTable[number[curr]].length;
i++)
{
output.push(hashTable[number[curr]][i]);
printWordsUtil(number, curr + 1, output, n);
output.pop();
if(number[curr] == 0 || number[curr] == 1)
return
}
}
// A wrapper over printWordsUtil(). It creates
// an output array and calls printWordsUtil()
function printWords(numbers, n)
{
printWordsUtil(number, 0, [], n);
}
// Driver code
let number = [ 2, 3, 4 ];
let n = number.length;
printWords(number, n);
// This code is contributed by avanitrachhadiya2155
</script>
|
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
پیچیدگی زمانی: O(4 n )، که در آن n تعداد ارقام در عدد ورودی است.
- هر رقم از یک عدد 3 یا 4 الفبا دارد، بنابراین می توان گفت که هر رقم دارای 4 الفبا به عنوان گزینه است.
- اگر n رقم باشد، 4 گزینه برای رقم اول و
- برای هر الفبای رقم اول 4 گزینه در رقم دوم وجود دارد، یعنی برای هر بازگشت 4 بازگشت دیگر فراخوانی می شود (اگر با حالت پایه مطابقت نداشته باشد).
- بنابراین پیچیدگی زمانی O(4n ) است .
فضای کمکی: O(n)
- هیچ ساختار داده اضافی به صراحت استفاده نمی شود، بنابراین ممکن است فکر کنید که فضای اضافی مورد نیاز نیست
- اما در یک تابع بازگشتی، پیچیدگی فضا به حداکثر عمق درخت بازگشتی بستگی دارد
- هر فراخوانی تابع یک قاب پشته جدید ایجاد می کند که متغیرها و پارامترهای محلی خود را ذخیره می کند
- درخت بازگشتی در اینجا دارای عمق n است، طول یک شاخه می تواند به این اندازه باشد
- بنابراین، پیچیدگی متناسب با n خواهد بود، یعنی O(n)
در ادامه، متن انگلیسی این مطلب را میتوانید مشاهده نمایید:
Given a keypad as shown in the diagram, and an n digit number, list all words which are possible by pressing these numbers.
Before the advent of QWERTY keyboards, texts and numbers were placed on the same key. For example, 2 has “ABC”, so if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. Below is a picture of such a keypad.
Examples:
Input: 234
Output: adg adh adi aeg aeh aei afg afh
afi bdg bdh bdi beg beh bei bfg
bfh bfi cdg cdh cdi ceg ceh cei
cfg cfh cfiExplanation: All possible words which can be
formed are (Alphabetical order):
adg adh adi aeg aeh aei afg afh
afi bdg bdh bdi beg beh bei bfg
bfh bfi cdg cdh cdi ceg ceh cei
cfg cfh cfi
If 2 is pressed then the alphabet can be a, b, c,
Similarly, for 3, it can be d, e, f, and for 4 can be g, h, i.Input: 5
Output: j k l
Explanation: All possible words which can be
formed are (Alphabetical order):
j, k, l, only these three alphabets
can be written with j, k, l.
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
Time Complexity: O(4n), where n is the number of digits in the input number.
- Each digit of a number has 3 or 4 alphabets, so it can be said that each digit has 4 alphabets as options.
- If there are n digits then there are 4 options for the first digit and
- for each alphabet of the first digit there are 4 options in the second digit, i.e for every recursion 4 more recursions are called (if it does not match the base case).
- So the time complexity is O(4n).
Auxiliary Space: O(n)
- No extra data structure is explicitly used, so one may think there is no extra space required
- But in a recursive function, the space complexity depends on the maximum depth of the recursion tree
- Each function call creates a new stack frame that stores its local variables and parameters
- The recursion tree here has a depth of n, that’s how long a branch can be
- Therefore, complexity will be proportional to n, that is O(n)
[/membership]