Home/ Questions/Q 830
Next
In Process

DevzConnect Latest Questions

Anthony Harding
  • 1
  • 1
Beginner
Asked: 2025-02-23T02:13:07+00:00 In:

Letter Combinations of a Phone Number – Leet code – medium

  • 1
  • 1

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"]

 

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].
interviewquestionsjavascriptleetcode
Share
Leave an answer

Leave an answer

Browse

1 Answer

  1. 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(''));
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’).