Skip to main content

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

  1. Create a function named generateWords that takes phoneNumber and keypadMapping as input.
  2. If the phoneNumber is empty, it means we have processed all the digits, so we print the current combination of characters and return.
  3. Otherwise, extract the first digit of the phoneNumber and store it in currentDigit.
  4. Get the remaining digits of the phoneNumber and store them in remainingDigits.
  5. Iterate through each character in keypadMapping[currentDigit] (characters associated with the current digit).
  6. Add the character to the currentCombination.
  7. Recursively call generateWords with remainingDigits and the updated currentCombination.
  8. 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.

Last updated on by Kalkicode




Comment

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