How to implement an algorithm to find letter combinations of a phone number ?
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"].
goli202084 Answered question
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 } }
goli202084 Answered question