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

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"].
Answered question
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 
    }
}

Answered question
Write your answer.

Categories