Print all possible words from phone digits
The given problem is to generate all possible words that can be formed by combining the characters associated with the digits on a phone keypad. Each digit on the keypad corresponds to a set of characters (e.g., digit 2 corresponds to 'ABC', digit 3 corresponds to 'DEF', etc.). The task is to generate all possible combinations of characters that can be formed using the given phone number.
Explanation with Example
Let's take an example to understand the problem better. Consider the phone number "786". The keypad mapping is as follows:
1 -> "" 2 -> "ABC" 3 -> "DEF" 4 -> "GHI" 5 -> "JKL" 6 -> "MNO" 7 -> "PQRS" 8 -> "TUV" 9 -> "WXYZ"
Now, we need to generate all possible words using the digits 7, 8, and 6. We start with the first digit, '7', which corresponds to "PQRS". For each character in "PQRS", we move to the next digit, '8', corresponding to "TUV", and combine each character with the characters we have generated so far. Finally, we move to the last digit, '6', corresponding to "MNO", and repeat the process. This way, we generate all possible combinations of characters, which will be the output.
Pseudocode
function generateWords(phoneNumber, keypadMapping):
if phoneNumber is empty:
print the current combination of characters
return
currentDigit = first digit of phoneNumber
remainingDigits = remaining digits of phoneNumber
for each character in keypadMapping[currentDigit]:
add character to currentCombination
generateWords(remainingDigits, keypadMapping)
remove last character from currentCombination
Algorithm Explanation
- Create a function named
generateWords
that takesphoneNumber
andkeypadMapping
as input. - If the
phoneNumber
is empty, it means we have processed all the digits, so we print the current combination of characters and return. - Otherwise, extract the first digit of the
phoneNumber
and store it incurrentDigit
. - Get the remaining digits of the
phoneNumber
and store them inremainingDigits
. - Iterate through each character in
keypadMapping[currentDigit]
(characters associated with the current digit). - Add the character to the
currentCombination
. - Recursively call
generateWords
withremainingDigits
and the updatedcurrentCombination
. - After the recursive call, remove the last character from
currentCombination
to backtrack and explore other combinations.
Code Solution
Here given code implementation process.
/*
C Program for
Print all possible words from phone digits
*/
#include <stdio.h>
#include <string.h>
// Print word combination
void word(const char * record [],char result[], const char *num, int n, int m, int i, int j)
{
if(i == m)
{
result[j] = '\0';
printf("\t%s",result);
return;
}
// Select number
int x = num[i] - '0';
if(x < n && strlen(record[x]) > 0)
{
for (int y = 0; y < strlen(record[x]); ++y)
{
result[j] = record[x][y];
word(record,result,num,n,m,i+1,j+1);
}
}
else
{
word(record,result,num,n,m,i+1,j);
}
}
// Handles the request of print all keypad combination of given number
void findWord(const char * record [], const char *num, int n)
{
int m = strlen(num);
if(m > 0)
{
char result[m+1];
printf("\n Given number : %s \n",num);
word(record,result,num,n,m,0,0);
}
}
int main()
{
// Keypad word of number of (1 to 9)
const char * record [] =
{
"", "","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"
};
int n = sizeof(record)/sizeof(record[0]);
const char *num1 = "786";
findWord(record,num1,n);
const char *num2 = "3242";
findWord(record,num2,n);
return 0;
}
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
/*
Java Program for
Print all possible words from phone digits
*/
class Words
{
// Print word combination
public void word(String[] record, String result, String num, int n, int m, int i, int j)
{
if (i == m)
{
System.out.print("\t" + result);
return;
}
// Select number
int x = num.charAt(i) - '0';
if (x < n && record[x].length() > 0)
{
for (int y = 0; y < record[x].length(); ++y)
{
word(record, result + record[x].charAt(y), num, n, m, i + 1, j + 1);
}
}
else
{
word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
public void findWord(String[] record, String num, int n)
{
int m = num.length();
if (m > 0)
{
String result = "";
System.out.print("\n Given number : " + num + " \n");
word(record, result, num, n, m, 0, 0);
}
}
public static void main(String[] args)
{
Words task = new Words();
// Keypad word of number of (1 to 9)
String[] record = {
"" , "" , "ABC" , "DEF" , "GHI" , "JKL" , "MNO" , "PQRS" , "TUV" , "WXYZ"
};
int n = record.length;
String num1 = "786";
task.findWord(record, num1, n);
String num2 = "3242";
task.findWord(record, num2, n);
}
}
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
// Include header file
#include <iostream>
#include<string.h>
using namespace std;
/*
C++ Program for
Print all possible words from phone digits
*/
class Words
{
public:
// Print word combination
void word(string record[], string result, string num, int n, int m, int i, int j)
{
if (i == m)
{
cout << "\t" << result;
return;
}
// Select number
int x = num[i] - '0';
if (x < n && record[x].size() > 0)
{
for (int y = 0; y < record[x].length(); ++y)
{
this->word(record, result + record[x][y], num, n, m, i + 1, j + 1);
}
}
else
{
this->word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
void findWord(string record[], string num, int n)
{
int m = num.size();
if (m > 0)
{
string result = "";
cout << "\n Given number : " << num << " \n";
this->word(record, result, num, n, m, 0, 0);
}
}
};
int main()
{
Words task = Words();
// Keypad word of number of (1 to 9)
string record[] = {
"" , "" , "ABC" , "DEF" , "GHI" , "JKL" , "MNO" , "PQRS" , "TUV" , "WXYZ"
};
int n = sizeof(record) / sizeof(record[0]);
string num1 = "786";
task.findWord(record, num1, n);
string num2 = "3242";
task.findWord(record, num2, n);
return 0;
}
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
// Include namespace system
using System;
/*
C# Program for
Print all possible words from phone digits
*/
public class Words
{
// Print word combination
public void word(String[] record, String result, String num, int n, int m, int i, int j)
{
if (i == m)
{
Console.Write("\t" + result);
return;
}
// Select number
int x = num[i] - '0';
if (x < n && record[x].Length > 0)
{
for (int y = 0; y < record[x].Length; ++y)
{
word(record, result + record[x][y], num, n, m, i + 1, j + 1);
}
}
else
{
word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
public void findWord(String[] record, String num, int n)
{
int m = num.Length;
if (m > 0)
{
String result = "";
Console.Write("\n Given number : " + num + " \n");
word(record, result, num, n, m, 0, 0);
}
}
public static void Main(String[] args)
{
Words task = new Words();
// Keypad word of number of (1 to 9)
String[] record = {
"" , "" , "ABC" , "DEF" , "GHI" , "JKL" , "MNO" , "PQRS" , "TUV" , "WXYZ"
};
int n = record.Length;
String num1 = "786";
task.findWord(record, num1, n);
String num2 = "3242";
task.findWord(record, num2, n);
}
}
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
<?php
/*
Php Program for
Print all possible words from phone digits
*/
class Words
{
// Print word combination
public function word( & $record, $result, $num, $n, $m, $i, $j)
{
if ($i == $m)
{
echo "\t". $result;
return;
}
// Select number
$x = ord($num[$i]) - ord('0');
if ($x < $n && strlen($record[$x]) > 0)
{
for ($y = 0; $y < strlen($record[$x]); ++$y)
{
$this->word($record, $result.$record[$x][$y], $num, $n, $m, $i + 1, $j + 1);
}
}
else
{
$this->word($record, $result, $num, $n, $m, $i + 1, $j);
}
}
// Handles the request of print all keypad combination of given number
public function findWord( & $record, $num, $n)
{
$m = strlen($num);
if ($m > 0)
{
$result = "";
echo "\n Given number : ". $num ." \n";
$this->word($record, $result, $num, $n, $m, 0, 0);
}
}
}
function main()
{
$task = new Words();
// Keypad word of number of (1 to 9)
$record = array("", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ");
$n = count($record);
$num1 = "786";
$task->findWord($record, $num1, $n);
$num2 = "3242";
$task->findWord($record, $num2, $n);
}
main();
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
/*
Node Js Program for
Print all possible words from phone digits
*/
class Words
{
// Print word combination
word(record, result, num, n, m, i, j)
{
if (i == m)
{
process.stdout.write("\t" + result);
return;
}
// Select number
var x = (num[i]).charCodeAt(0) - ('0').charCodeAt(0);
if (x < n && record[x].length > 0)
{
for (var y = 0; y < record[x].length; ++y)
{
this.word(record, result + record[x][y], num, n, m, i + 1, j + 1);
}
}
else
{
this.word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
findWord(record, num, n)
{
var m = num.length;
if (m > 0)
{
var result = "";
process.stdout.write("\n Given number : " + num + " \n");
this.word(record, result, num, n, m, 0, 0);
}
}
}
function main()
{
var task = new Words();
// Keypad word of number of (1 to 9)
var record = ["", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"];
var n = record.length;
var num1 = "786";
task.findWord(record, num1, n);
var num2 = "3242";
task.findWord(record, num2, n);
}
main();
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
# Python 3 Program for
# Print all possible words from phone digits
class Words :
# Print word combination
def word(self, record, result, num, n, m, i, j) :
if (i == m) :
print("\t", result, end = "")
return
# Select number
x = ord(num[i]) - ord('0')
if (x < n and len(record[x]) > 0) :
y = 0
while (y < len(record[x])) :
self.word(record, result + record[x][y], num, n, m, i + 1, j + 1)
y += 1
else :
self.word(record, result, num, n, m, i + 1, j)
# Handles the request of print all keypad combination of given number
def findWord(self, record, num, n) :
m = len(num)
if (m > 0) :
result = ""
print("\n Given number : ", num ," ")
self.word(record, result, num, n, m, 0, 0)
def main() :
task = Words()
# Keypad word of number of (1 to 9)
record = ["", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"]
n = len(record)
num1 = "786"
task.findWord(record, num1, n)
num2 = "3242"
task.findWord(record, num2, n)
if __name__ == "__main__": main()
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
# Ruby Program for
# Print all possible words from phone digits
class Words
# Print word combination
def word(record, result, num, n, m, i, j)
if (i == m)
print("\t", result)
return
end
# Select number
x = (num[i]).ord - ('0').ord
if (x < n && record[x].length() > 0)
y = 0
while (y < record[x].length())
self.word(record, result + record[x][y], num, n, m, i + 1, j + 1)
y += 1
end
else
self.word(record, result, num, n, m, i + 1, j)
end
end
# Handles the request of print all keypad combination of given number
def findWord(record, num, n)
m = num.length()
if (m > 0)
result = ""
print("\n Given number : ", num ," \n")
self.word(record, result, num, n, m, 0, 0)
end
end
end
def main()
task = Words.new()
# Keypad word of number of (1 to 9)
record = ["", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"]
n = record.length
num1 = "786"
task.findWord(record, num1, n)
num2 = "3242"
task.findWord(record, num2, n)
end
main()
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
/*
Scala Program for
Print all possible words from phone digits
*/
class Words
{
// Print word combination
def word(record: Array[String], result: String, num: String, n: Int, m: Int, i: Int, j: Int): Unit = {
if (i == m)
{
print("\t" + result);
return;
}
// Select number
var x: Int = num(i) - '0';
if (x < n && record(x).length() > 0)
{
var y: Int = 0;
while (y < record(x).length())
{
this.word(record, result + record(x)(y), num, n, m, i + 1, j + 1);
y += 1;
}
}
else
{
this.word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
def findWord(record: Array[String], num: String, n: Int): Unit = {
var m: Int = num.length();
if (m > 0)
{
var result: String = "";
print("\n Given number : " + num + " \n");
this.word(record, result, num, n, m, 0, 0);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Words = new Words();
// Keypad word of number of (1 to 9)
var record: Array[String] = Array("", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ");
var n: Int = record.length;
var num1: String = "786";
task.findWord(record, num1, n);
var num2: String = "3242";
task.findWord(record, num2, n);
}
}
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
/*
Swift 4 Program for
Print all possible words from phone digits
*/
class Words
{
// Print word combination
func word(_ record: [String], _ result: String, _ num: String, _ n: Int, _ m: Int, _ i: Int, _ j: Int)
{
if (i == m)
{
print("\t", result, terminator: "");
return;
}
// Select number
let x: Int = Int(UnicodeScalar(String(Array(num)[i]))!.value - UnicodeScalar("0")!.value);
if (x < n && record[x].count > 0)
{
var y: Int = 0;
while (y < record[x].count)
{
self.word(record, result + String(Array(record[x])[y]), num, n, m, i + 1, j + 1);
y += 1;
}
}
else
{
self.word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
func findWord(_ record: [String], _ num: String, _ n: Int)
{
let m: Int = num.count;
if (m > 0)
{
let result: String = "";
print("\n Given number : ", num ," ");
self.word(record, result, num, n, m, 0, 0);
}
}
}
func main()
{
let task: Words = Words();
// Keypad word of number of (1 to 9)
let record: [String] = ["", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"];
let n: Int = record.count;
let num1: String = "786";
task.findWord(record, num1, n);
let num2: String = "3242";
task.findWord(record, num2, n);
}
main();
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
/*
Kotlin Program for
Print all possible words from phone digits
*/
class Words
{
// Print word combination
fun word(record: Array < String > , result: String, num: String, n: Int, m: Int, i: Int, j: Int): Unit
{
if (i == m)
{
print("\t" + result);
return;
}
// Select number
var x: Int = num[i] - '0';
if (x < n && record[x].count() > 0)
{
var y: Int = 0;
while (y < record[x].count())
{
this.word(record, result + record[x][y], num, n, m, i + 1, j + 1);
y += 1;
}
}
else
{
this.word(record, result, num, n, m, i + 1, j);
}
}
// Handles the request of print all keypad combination of given number
fun findWord(record: Array < String > , num: String, n: Int): Unit
{
var m: Int = num.count();
if (m > 0)
{
var result: String = "";
print("\n Given number : " + num + " \n");
this.word(record, result, num, n, m, 0, 0);
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Words = Words();
// Keypad word of number of (1 to 9)
var record: Array < String > = arrayOf("", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ");
var n: Int = record.count();
var num1: String = "786";
task.findWord(record, num1, n);
var num2: String = "3242";
task.findWord(record, num2, n);
}
Output
Given number : 786
PTM PTN PTO PUM PUN PUO PVM PVN PVO QTM QTN QTO QUM QUN QUO QVM QVN QVO RTM RTN RTO RUM RUN RUO RVM RVN RVO STM STN STO SUM SUN SUO SVM SVN SVO
Given number : 3242
DAGA DAGB DAGC DAHA DAHB DAHC DAIA DAIB DAIC DBGA DBGB DBGC DBHA DBHB DBHC DBIA DBIB DBIC DCGA DCGB DCGC DCHA DCHB DCHC DCIA DCIB DCIC EAGA EAGB EAGC EAHA EAHB EAHC EAIA EAIB EAIC EBGA EBGB EBGC EBHA EBHB EBHC EBIA EBIB EBIC ECGA ECGB ECGC ECHA ECHB ECHC ECIA ECIB ECIC FAGA FAGB FAGC FAHA FAHB FAHC FAIA FAIB FAIC FBGA FBGB FBGC FBHA FBHB FBHC FBIA FBIB FBIC FCGA FCGB FCGC FCHA FCHB FCHC FCIA FCIB FCIC
Time Complexity
The time complexity of this algorithm depends on the number of characters associated with each digit on the phone keypad. Suppose the average number of characters per digit is 'k'. In that case, the time complexity can be approximated as O(k^N), where 'N' is the number of digits in the phone number. This is because for each digit, we have 'k' choices, and we need to process 'N' digits in total. Therefore, the number of recursive calls will be k * k * k * ... (N times) = k^N.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment