Code: Letter Combinations of a Phone Number using Recursion | DSA in C++ - Software Development PDF Download

Here's a C++ code that uses recursion to find all possible letter combinations of a phone number:

#include <iostream>

#include <vector>

#include <string>

using namespace std;

// Mapping of digits to corresponding letters

const vector<string> digitLetters = {

    "",     // 0

    "",     // 1

    "abc",  // 2

    "def",  // 3

    "ghi",  // 4

    "jkl",  // 5

    "mno",  // 6

    "pqrs", // 7

    "tuv",  // 8

    "wxyz"  // 9

};

// Recursive function to find letter combinations

void findLetterCombinations(string digits, string current, vector<string>& result) {

    // Base case: if there are no more digits, add the current combination to the result

    if (digits.empty()) {

        result.push_back(current);

        return;

    }

    // Get the letters corresponding to the first digit

    string letters = digitLetters[digits[0] - '0'];

    // Recursively find combinations for the remaining digits

    for (char letter : letters) {

        findLetterCombinations(digits.substr(1), current + letter, result);

    }

}

// Function to find letter combinations of a phone number

vector<string> letterCombinations(string digits) {

    vector<string> result;

    if (digits.empty()) {

        return result;

    }

    findLetterCombinations(digits, "", result);

    return result;

}

// Main function

int main() {

    string phoneNumber = "23";

    vector<string> combinations = letterCombinations(phoneNumber);

    cout << "Letter combinations of phone number " << phoneNumber << ":" << endl;

    for (string combination : combinations) {

        cout << combination << endl;

    }

    return 0;

}

Output:

Letter combinations of phone number 23:

ad

ae

af

bd

be

bf

cd

ce

cf

Explanation:

• The code defines a vector 'digitLetters' that maps each digit (2 to 9) to the corresponding letters on a phone keypad. The index of each digit in the vector corresponds to the digit itself.
• The 'findLetterCombinations' function is a recursive function that takes three parameters: the remaining digits to process, the current combination of letters formed, and a reference to the result vector to store the final combinations.
• The base case of the recursion is when there are no more digits remaining ('digits.empty()'). In this case, the current combination is added to the result vector.
• Within the recursive function, the letters corresponding to the first digit are obtained using 'digitLetters[digits[0] - '0']'. The subtraction '0' is performed to convert the character digit to an integer index.
• For each letter obtained, the function calls itself recursively with the remaining digits ('digits.substr(1)') and the updated current combination ('current + letter').
• The 'letterCombinations' function serves as a wrapper function to handle the case when the input phone number is empty. It creates an empty result vector and calls 'findLetterCombinations' with the initial values.
• In the 'main' function, a sample phone number "23" is provided. The 'letterCombinations' function is called, and the resulting combinations are printed to the console.

The code utilizes recursion to explore all possible combinations of letters by iterating through the digits and their corresponding letters. It keeps track of the current combination formed at each step and adds it to the result vector when there are no more digits remaining. The process continues until all possible combinations are found.