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

Example 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Java Solution
class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return new ArrayList<>();
}
Map<Character, String> digitToLetters = new HashMap<>();
digitToLetters.put('2', "abc");
digitToLetters.put('3', "def");
digitToLetters.put('4', "ghi");
digitToLetters.put('5', "jkl");
digitToLetters.put('6', "mno");
digitToLetters.put('7', "pqrs");
digitToLetters.put('8', "tuv");
digitToLetters.put('9', "wxyz");
List<String> result = new ArrayList<>();
backtrack(digits, 0, new StringBuilder(), result, digitToLetters);
return result;
}
private void backtrack(String digits, int index, StringBuilder path, List<String> result, Map<Character, String> digitToLetters) {
if (index == digits.length()) {
result.add(path.toString());
return;
}
char digit = digits.charAt(index);
String letters = digitToLetters.get(digit);
for (char letter : letters.toCharArray()) {
path.append(letter);
backtrack(digits, index + 1, path, result, digitToLetters);
path.deleteCharAt(path.length() - 1);
}
}
}
C++ Solution
//
// Created by robert on 12/20/24.
//
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void backtrack(string & digits, const int index, string & current, vector<string> & result, const unordered_map<char,string> & map) {
if (digits.length() == index) {
result.push_back(current);
return;
}
char digit = digits[index];
string letters = map.find(digit)->second;
for( char letter : letters ) {
current.push_back(letter);
backtrack( digits, index+1, current, result, map );
current.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> result;
string current;
if (digits.empty()) return result;
unordered_map<char, string> map;
map.insert(make_pair('2', "abc"));
map.insert(make_pair('3', "def"));
map.insert(make_pair('4', "ghi"));
map.insert(make_pair('5', "jkl"));
map.insert(make_pair('6', "mno"));
map.insert(make_pair('7', "pqrs"));
map.insert(make_pair('8', "tuv"));
map.insert(make_pair('9', "wxyz"));
backtrack(digits, 0, current, result, map);
return result;
}
int main(){
vector<string> result = letterCombinations("23");
for (const auto & i : result) {
cout << i << endl;
}
}