Letter Combinations of a Phone Number - C Solution

1. Introduction

This blog post explores a fascinating problem in C programming: generating all possible letter combinations that a given string of digits could represent, similar to the letters on a telephone keypad. This problem not only demonstrates the utility of recursive algorithms but also offers a practical application in systems like SMS and dial-pad-based searching.

Problem

Given a string containing digits from 2-9, we need to find all possible letter combinations that these numbers could represent, based on the mapping found on a telephone keypad. This problem is akin to finding all permutations of these letters, a classic example of using recursion in problem-solving.

2. Solution Steps

1. Define a recursive function to generate combinations.

2. Map each digit to its corresponding letters, as on a telephone keypad.

3. Add a combination to the result when the end of the digit string is reached.

4. Explore each letter option for each digit, recursively calling the function for the next digit.

3. Code Program

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

// Function to recursively generate combinations
void generateCombinations(char *digits, int index, char *current, int currentSize, char **result, int *returnSize, char phoneMap[10][5]) {
    // Base case: if end of digits string is reached
    if (index == strlen(digits)) {
        current[currentSize] = '\0'; // Null terminate the current combination
        result[*returnSize] = strdup(current); // Add combination to result
        (*returnSize)++; // Increment size of result array
        return;
    }

    // Get the corresponding letters for the current digit
    char *letters = phoneMap[digits[index] - '0'];
    for (int i = 0; letters[i]; i++) {
        current[currentSize] = letters[i]; // Add letter to current combination
        // Recursively call for next digit
        generateCombinations(digits, index + 1, current, currentSize + 1, result, returnSize, phoneMap);
    }
}

// Function to return all combinations
char **letterCombinations(char *digits, int *returnSize) {
    // Edge case: empty input
    if (*digits == '\0') {
        *returnSize = 0;
        return NULL;
    }

    char phoneMap[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    char **result = malloc(256 * sizeof(char *)); // Allocate memory for results
    char current[20]; // Current combination
    *returnSize = 0; // Initialize returnSize
    generateCombinations(digits, 0, current, 0, result, returnSize, phoneMap);
    return result;
}

int main() {
    char digits[] = "23";
    int returnSize;
    char **combinations = letterCombinations(digits, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", combinations[i]);
        free(combinations[i]); // Free each string
    }
    free(combinations); // Free the array
    return 0;
}

Output:

ad
ae
af
bd
be
bf
cd
ce
cf

Explanation:

The program starts by mapping each digit to its corresponding letters. 

The generateCombinations function is called recursively to explore all possible letter combinations. 

For each digit, it iterates through its possible letters, appending them to the current combination. 

Once the end of the digits string is reached, the current combination is added to the results. 

The main function tests this with the digits "23", producing all combinations like 'ad', 'ae', 'af', and so on, corresponding to the possible letters for '2' and '3' on a phone keypad.