Iterative Letter Combinations of a Phone Number -

Spread the love

Print all conceivable letter combinations the integers could represent from an integer array with digits from [0, 9].

Following a mapping of digits to letters, much as on phone buttons. 0 and 1 do not map to any letters, by note. The picture below shows every mapping point:

Example:

Input: arr[] = {2, 3}
Output: ad ae af bd be bf cd ce cf

Input: arr[] = {9}
Output: w x y z

Simple Answer: Recursive
The concept is basic; we examine each digit one by one. We progressively add all mappings of the remaining digits after obtaining all mappings of the current digit.

Taking index as an argument, we create a recursive function letter combinations). We one by one map all instances of current characters to res and recursively call for the next index.

Table of Contents

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void letterCombinations(const vector<int> &a, vector<string> &mp, 
                        int i, string curr, vector<string> &res)
{
    // If we have used a mapping for
    // every digit
    if (i == a.size())
    {
        res.push_back(curr);
        return;
    }

    // Get all characters mapped to current
    // digit. 
    string chars = mp[a[i]];
  
    // Add every character to the res and make
    // a recursive call for the next digit.
    for (char c : chars)
        letterCombinations(a, mp, i + 1, curr + c, res);
}

// Function to find list of all words possible by pressing given numbers.
vector<string> possibleWords(const vector<int> &a)
{
    vector<string> mp = {"", "", "abc", "def", "ghi", 
                         "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
    letterCombinations(a, mp, 0, "", res);
    return res;
}

int main()
{
    vector<int> a = {2, 3};
    vector<string> res = possibleWords(a);
    for (const string &word : res)
        cout << word << " ";
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void letterCombinations(int* a, int size, char** mp, int i, char* curr, char** res, int* resSize) {
  
    // If we have used a mapping for every digit
    if (i == size) {
        res[*resSize] = malloc(strlen(curr) + 1);
        strcpy(res[*resSize], curr);
        (*resSize)++;
        return;
    }

    // Get all characters mapped to current digit
    char* chars = mp[a[i]];

    // Add every character to the res and make a recursive call for the next digit
    for (int j = 0; chars[j] != '\0'; j++) {
        char newCurr[100];
        strcpy(newCurr, curr);
        size_t len = strlen(newCurr);
        newCurr[len] = chars[j];
        newCurr[len + 1] = '\0';
        letterCombinations(a, size, mp, i + 1, newCurr, res, resSize);
    }
}

// Function to find list of all words possible by pressing given numbers
char** possibleWords(int* a, int size, int* returnSize) {
    char* mp[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    char** res = malloc(1000 * sizeof(char*)); // Adjust size as needed
    *returnSize = 0;
    letterCombinations(a, size, mp, 0, "", res, returnSize);
    return res;
}

// Driver code
int main() {
    int a[] = {2, 3};
    int size = sizeof(a) / sizeof(a[0]);
    int returnSize;
    char** res = possibleWords(a, size, &returnSize);

    for (int i = 0; i < returnSize; i++) {
        printf("%s ", res[i]);
        free(res[i]);
    }
    free(res);
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

public class GfG {

    // Recursive function to find all letter combinations
    private static void letterCombinations(int[] a, String[] mp, int i, String curr, List<String> res) {
      
        // If we have used a mapping for every digit
        if (i == a.length) {
            res.add(curr);
            return;
        }

        // Get all characters mapped to current digit
        String chars = mp[a[i]];

        // Add every character to the res and make a recursive call for the next digit
        for (char c : chars.toCharArray())
            letterCombinations(a, mp, i + 1, curr + c, res);
    }

    // Function to find list of all words possible by pressing given numbers
    public static List<String> possibleWords(int[] a) {
        String[] mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> res = new ArrayList<>();
        letterCombinations(a, mp, 0, "", res);
        return res;
    }

    // Driver code
    public static void main(String[] args) {
        int[] a = {2, 3};
        List<String> res = possibleWords(a);
        for (String word : res)
            System.out.print(word + " ");
    }
}

Python

# Recursive function to find all letter combinations
def letter_combinations(a, mp, i, curr, res):
  
    # If we have used a mapping for every digit
    if i == len(a):
        res.append(curr)
        return

    # Get all characters mapped to current digit
    chars = mp[a[i]]

    # Add every character to the res and make a recursive call for the next digit
    for c in chars:
        letter_combinations(a, mp, i + 1, curr + c, res)

# Function to find list of all words possible by pressing given numbers
def possible_words(a):
    mp = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    res = []
    letter_combinations(a, mp, 0, "", res)
    return res

# Driver code
a = [2, 3]
res = possible_words(a)
print(" ".join(res))

JS

// Recursive function to find all letter combinations
function letterCombinations(a, mp, i, curr, res) {

    // If we have used a mapping for every digit
    if (i === a.length) {
        res.push(curr);
        return;
    }

    // Get all characters mapped to current digit
    const chars = mp[a[i]];

    // Add every character to the res and make a recursive call for the next digit
    for (const c of chars) {
        letterCombinations(a, mp, i + 1, curr + c, res);
    }
}

// Function to find list of all words possible by pressing given numbers
function possibleWords(a) {
    const mp = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    const res = [];
    letterCombinations(a, mp, 0, "", res);
    return res;
}

// Driver code
const a = [2, 3];
const res = possibleWords(a);
console.log(res.join(" "));

Output

ad ae af bd be bf cd ce cf