Letter Combinations of a Phone Number Problem and Solution

1. Introduction

A comprehensive guide to solving the "Letter Combinations of a Phone Number" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Letter Combinations of a Phone Number" problem involves generating all possible letter combinations that the number could represent, based on the layout of letters on a telephone keypad.

2. Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

3. Solution in C++

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

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector<string> res;
    vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    res.push_back("");
    for (char digit : digits) {
        vector<string> temp;
        for (string t : res) {
            string letters = mapping[digit - '0'];
            for (char letter : letters) {
                temp.push_back(t + letter);
            }
        }
        res.swap(temp);
    }
    return res;
}

// Example usage
int main() {
    string digits = "23";
    auto combinations = letterCombinations(digits);
    for (string combo : combinations) {
        cout << combo << " ";
    }
    cout << endl;
    return 0;
}

Output:

ad ae af bd be bf cd ce cf

Explanation:

1. letterCombinations in C++ uses iterative approach.

2. It iterates through each digit and generates all possible combinations with the existing ones.

3. Uses a vector to store intermediate and final results.

4. Solution in Java

import java.util.*;

public class LetterCombinationsPhoneNumber {
    public static List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return Collections.emptyList();
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        LinkedList<String> res = new LinkedList<>();
        res.add("");
        for (int i = 0; i < digits.length(); i++) {
            int index = Character.getNumericValue(digits.charAt(i));
            while (res.peek().length() == i) {
                String t = res.remove();
                for (char c : mapping[index].toCharArray()) {
                    res.add(t + c);
                }
            }
        }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        String digits = "23";
        List<String> combinations = letterCombinations(digits);
        System.out.println(combinations);
    }
}

Output:

[ad, ae, af, bd, be, bf, cd, ce, cf]

Explanation:

1. Java's letterCombinations uses a LinkedList to store intermediate results.

2. Iterates over each digit, expanding the combinations list with the corresponding characters.

3. The final result is the list of all combinations.

5. Solution in Python

def letter_combinations(digits):
    if not digits:
        return []
    mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    res = [""]
    for digit in digits:
        temp = []
        for t in res:
            for letter in mapping[int(digit)]:
                temp.append(t + letter)
        res = temp
    return res

# Example usage
digits = "23"
print("Combinations:", letter_combinations(digits))

Output:

Combinations: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Explanation:

1. Python's letter_combinations function follows a similar iterative approach.

2. Builds combinations by iterating over each digit and appending corresponding characters.

3. Stores all intermediate and final combinations in a list.