Posted on

Letter Combinations of a phone number

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;
}
}