https://algo.monster/problems/letter_combinations_of_phone_number
There should be a test case with duplicate numbers, e.g. “565” (try in custom test). I thought solution to Permutations worked here but I was wrong.
Alternative solution for Javascript:
function letterCombinationsOfPhoneNumber(digits) {
let table = {2:‘abc’, 3:‘def’, 4: ‘ghi’, 5:‘jkl’, 6:‘mno’, 7:‘pqrs’, 8:‘tuv’, 9:‘wxyz’}
let path = []
let res = []
let unused = []
function dfs(unused, res, path){
if(path.length === digits.length){
return res.push(path.join(''))
}
for(let letters of unused){
unused = unused.filter(str => str !== letters)
for(let letter of letters){
path.push(letter)
dfs(unused, res, path)
path.pop()
}
}
}
for(let digit of digits){
unused.push(table[digit])
}
dfs(unused, res, path)
return res;
}
It seems we don’t need a “used/unused” map/object/array here in contrast to the permutations problem.
In the permutations problem, we had to go back to the same arr, but our choices kept being reduced.
In this problem, we are able to go through each letter per digit consecutively.
Good job on catching duplicate numbers. You were right that most of the permutations concept can be used to solve this problem with a few changes. The concept of tracking ‘used’ letters here will reduce the number of results, so we will have issues with duplicate numbers.
The solution also doesn’t do that great of a job at explaining that the length of the current path helps establish what digit we are exploring.
At every dfs call, we need to establish what digit in the number we are looking at (i.e. ‘56’ gives us index 0 which is 5, and index 1 which is 6). We want to iterate through all of our letter options for each index. At index 0, we have 5, so we will look at the array [j, k, l]. If our path list/array/vector already has a letter in it, that means we are now exploring each letter option for number 6 (index 1) - this means we are on our second level in the dfs tree.
C# Solution
private static Dictionary<char, char[]> KEYBOARD = new Dictionary<char, char[]>{
{'2', "abc".ToCharArray()},
{'3', "def".ToCharArray()},
{'4', "ghi".ToCharArray()},
{'5', "jkl".ToCharArray()},
{'6', "mno".ToCharArray()},
{'7', "pqrs".ToCharArray()},
{'8', "tuv".ToCharArray()},
{'9', "wxyz".ToCharArray()}}
;
private static void dfs(StringBuilder path, List<String> res, char[] digits) {
if (path.Length == digits.Length) {
res.Add(path.ToString());
return;
}
char next_digit = digits[path.Length];
foreach (char letter in KEYBOARD[next_digit]) {
path.Append(letter);
dfs(path, res, digits);
path.Remove(path.Length - 1,1);
}
}
public static List<string> LetterCombinationsOfPhoneNumber(string digits)
{
var res = new List<String>();
dfs(new StringBuilder(), res, digits.ToCharArray());
return res;
}
thank you for the explanation that was helpful
Not exactly. Your solution will contain the 4^n combination of n letters. That’s O(n * 4^n) complexity which is the biggest one. That’s the response.
Easier to understand, java
public static List<String> letterCombinationsOfPhoneNumber(String digits) {
// WRITE YOUR BRILLIANT CODE HERE
Map<Character,String> mapping = new HashMap();
mapping.put('0',"");
mapping.put('1',"");
mapping.put('2',"abc");
mapping.put('3',"def");
mapping.put('4',"ghi");
mapping.put('5',"jkl");
mapping.put('6',"mno");
mapping.put('7',"pqrs");
mapping.put('8',"tuv");
mapping.put('9',"wxyz");
List<String> result = new ArrayList();
dfs(new StringBuilder(), 0, mapping , result, digits);
return result;
}
private static void dfs(StringBuilder current, int index, Map<Character,String> mapping,List<String> result,String digits)
{
if(index == digits.length())
{
result.add(current.toString());
return;
}
char number = digits.charAt(index);
for(char c: mapping.get(number).toCharArray()){
current.append(c);
dfs(current,index + 1,mapping,result,digits);
current.deleteCharAt(current.length() - 1);
}
}
Structured Programming JS Solution:
const KEYBOARD = {
'2': ["a", "b", "c"],
'3': ["d", "e", "f"],
'4': ["g", "h", "i"],
'5': ["j", "k", "l"],
'6': ["m", "n", "o"],
'7': ["p", "q", "r", "s"],
'8': ["t", "u", "v"],
'9': ["w", "x", "y", "z"],
};
function letterCombinationsOfPhoneNumber(digits) {
let results = [];
if (digits.length >= 1) {
const char = digits.charAt(0);
const substr = digits.substr(1);
for (const letter of KEYBOARD[char]) {
if (substr.length) {
const combos = letterCombinationsOfPhoneNumber(substr);
combos.forEach((combo) => results.push(`${letter}${combo}`));
} else {
results.push(letter);
}
}
}
return results;
}
Python:
def letter_combinations_of_phone_number(digits: str) → List[str]:
digits_to_letters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
output = []
def get_edges(index):
return digits_to_letters[int(index)]
n = len(digits)
def dfs(current_idx: int, path: List[str]):
if current_idx >= n:
output.append(''.join(path))
return
for edge in get_edges(digits[current_idx]):
path.append(edge)
dfs(current_idx + 1, path)
path.pop()
dfs(0, [])
return output
I think on the template it should be ‘report(path)’ instead of ‘report(edge)’
you are right, it’ll be updated in the next deploy
Does O(4^n * n) simplify down, or is that the expected time complexity answer in an interview?
Optimized C++ solution avoiding the string copies (extra memory use) on the recursive argument:
const std::unordered_map key2letters { {'1', ""}, {'2', "abc"}, {'3', "def"},
{'4', "ghi"}, {'5', "jkl" },
{'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"} };
void lcopn(std::vector& res, const std::string& digits, std::string& path, int i) {
if (path.size() == digits.size()) {
res.emplace_back(path);
} else {
char digit = digits[i];
std::string letters = key2letters.at(digit);
for(char l : letters) {
path.push_back(l);
lcopn(res, digits, path, i+1);
path.pop_back();
}
}
}
am I the only one not ever understanding how the problem is formulated? only by checking the solution I can finally understand the statement…
def letter_combinations_of_phone_number(digits: str) -> List[str]:
phone_keyboard_map = [
[],
['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i'],
['j', 'k', 'l'],
['m', 'n', 'o'],
['p', 'q', 'r', 's'],
['t', 'u', 'v'],
['w', 'x', 'y', 'z'],
]
def dfs(cur_path, idx, digits, rst):
if idx == len(digits):
rst.append(''.join(cur_path))
return
num = int(digits[idx])
for letter in phone_keyboard_map[num - 1]:
cur_path.append(letter)
dfs(cur_path, idx + 1, digits, rst)
cur_path.pop()
rst = []
dfs([], 0, digits, rst)
return rst
Regarding the time complexity, 4^n gives the number of leaf nodes, not the total nodes in the tree. Did you intentionally round down to simplify?
Python approach, easier to understand:
def letter_combinations_of_phone_number(digits: str) -> List[str]:
comb= {2: ['a','b','c'],
3: ['d','e','f'],
4: ['g','h','i'],
5: ['j','k','l'],
6: ['m','n','o'],
7: ['p','q','r','s'],
8: ['t','u','v'],
9: ['w','x','y','z']
}
if len(digits) ==0:
return ['']
digitList = list(digits)
def helper(level, path, res):
if level == len(digits):
res.append(path)
return
for letter in comb[int(digitList[level])]:
currentPath = path + letter
helper(level+1, currentPath, res)
return res
res = helper(0, '', [])
return res
Typo on the leaf node of the example tree, it should be ‘cd’ instead of ‘ed’