Letter Combinations of a Phone Number - CPP Solution

1. Introduction

This blog post focuses on solving a classic problem often encountered in coding interviews - generating all possible letter combinations of a phone number. The problem is based on the old mobile phone keypads, where each digit from 2 to 9 is mapped to a set of letters.

Problem

Given a string containing digits from 2-9 inclusive, we are required to return all possible letter combinations that the number could represent. The challenge lies in generating these combinations efficiently and accurately.

2. Solution Steps

1. Create a mapping of digits to their corresponding letters.

2. Use a recursive approach to generate all combinations.

3. For each digit in the input string, iterate over its corresponding letters.

4. Add each letter to the current combination and recurse for the next digit.

5. Once the end of the string is reached, add the current combination to the result.

6. Return all generated combinations.

3. Code Program

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

// Function to generate letter combinations for a phone number
void backtrack(const string &digits, const vector<string> &phoneMap, string &current, int index, vector<string> &combinations) {
    if (index == digits.length()) {
        combinations.push_back(current);
        return;
    }
    string letters = phoneMap[digits[index] - '0'];
    for (char letter : letters) {
        current.push_back(letter); // Add the letter to the current combination
        backtrack(digits, phoneMap, current, index + 1, combinations); // Recurse for the next digit
        current.pop_back(); // Remove the letter to backtrack
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector<string> phoneMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> combinations;
    string current;
    backtrack(digits, phoneMap, current, 0, combinations);
    return combinations;
}

int main() {
    string digits = "23";
    vector<string> result = letterCombinations(digits);
    cout << "Combinations are: ";
    for (const string &comb : result) {
        cout << comb << " ";
    }
    cout << endl;
    return 0;
}

Output:

Combinations are: ad ae af bd be bf cd ce cf

Explanation:

1. The input "23" maps to letters {'a', 'b', 'c'} for '2' and {'d', 'e', 'f'} for '3'.

2. The function generates all combinations by picking a letter for each digit.

3. It starts with 'a', then recurses to add 'd', 'e', and 'f', forming "ad", "ae", "af".

4. This process repeats for 'b' and 'c', generating "bd", "be", "bf", "cd", "ce", "cf".

5. The recursive approach ensures all combinations are explored and collected.

6. The output is a list of all valid combinations formed from the input digits.