# How to implement an algorithm to find letter combinations of a phone number ?

5.27K views
0

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

0

Below is a Javascript Solution to this problem using Depth first search traversal !!

/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
var digitMap = ['0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
var prefix = [];
var result = [];
if (digits.length) {
dfs(0, prefix, digits, result, digitMap);
}
return result;
};
var dfs = function(index, prefix, digits, result, map) {
if (index === digits.length)
return result.push(prefix.join(''));
var str = map[digits[index] - '0']; // remove ASCII bias from string to get decimal value
for (var i = 0; i < str.length; i++) {
prefix.push(str[i]);    // push the characters
dfs(index+1, prefix, digits, result, map);  // recursive DFS call
prefix.pop(); // move to the next subsequence after current one is complete
}
}