Home/ naveendk/Answers
  1. Asked: February 23, 2025In:

    Letter Combinations of a Phone Number – Leet code – medium

    naveendk
    naveendk Beginner

    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:

    1. Base Case:
      If digits is empty, return an empty array.

    2. phoneMap:
      Maps each digit (2-9) to its corresponding letters.

    3. 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:

    ["ad","ae","af","bd","be","bf","cd","ce","cf"]
    []
    ["a","b","c"]

    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