naveendk

Asked: February 23, 2025In: JavaScript

Letter Combinations of a Phone Number – Leet code – medium

naveendk Beginner

Added an answer on February 23, 2025 at 2:21 am

function letterCombinations(digits) { if (!digits) return []; const phoneMap = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" }; const result = []; const backtrack = (index, path) => { if (path.length === digits.length) { result.push(path.join('Read more

function letterCombinations(digits) {
if (!digits) return [];

const phoneMap = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
};

const result = [];

const backtrack = (index, path) => {
if (path.length === digits.length) {
result.push(path.join(''));
return;
}

const possibleLetters = phoneMap[digits[index]];
for (let letter of possibleLetters) {
path.push(letter); // Choose
backtrack(index + 1, path); // Explore
path.pop(); // Un-choose (backtrack)
}
};

backtrack(0, []);
return result;
}

// Example usage:
console.log(letterCombinations("23")); // ["ad","ae","af","bd","be","bf","cd","ce","cf"]
console.log(letterCombinations("")); // []
console.log(letterCombinations("2")); // ["a","b","c"]

Explanation:

Base Case:
If digits is empty, return an empty array.
phoneMap:
Maps each digit (2-9) to its corresponding letters.
Backtracking (backtrack):
- index: Tracks the current position in the digits string.
- path: Holds the current combination as an array of characters.
- If path.length equals digits.length, it forms a valid combination and is pushed to result.
- Loops through possible letters for the current digit, recursively explores further, and backtracks by popping the last letter.

Output:

This solution uses DFS (Depth-First Search) with backtracking and has a time complexity of O(4^n), where n is the length of digits (since some digits map to up to 4 letters, e.g., ‘7’ and ‘9’).

See less