17_letter_combinations_phone_number

dz / leetcode / 17_letter_combinations_phone_number

Summary

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. 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.

Node Tree

• editorial
  • lock_in_letters
  • recursion_reason_why_digits_size_small
  • recursive_solution
    • recursion_explanation
  • solutions_mine_vs_theirs
  • backtracking_function
• intuition
  • flatten_loop
    • counter
  • lookup_table
• URL

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/letter-combinations-of-a-phone-number/

intuition
content	Combinatorial problem (I think I have the terminology correct). My gut says this is mostly about setting up the loops properly. The first digit has 3-4 possible letters, then the second has 3-4, then the next, etc. Limit is 4 digit.
children	flatten_loop, lookup_table

flatten_loop
content	You could compute the number of combinations ahead of time. For instance, "23" should have 3^2 or 9 combinations. a loop would need to run exactly 9 times to get all the combinations
children	counter (State managed in the loop)
parents	intuition

counter
content	You could keep track of state in a fixed-array as a kind of counter, where every digit goes 0,1,2 or 0,1,2,3 depending on size. Every time the rightmost digit goes back to zero, update every other digit. It's sort of like a weird base number system that's mostly base 3.
parents	flatten_loop

lookup_table
content	Lookup table for numbers is needed. You really just need an array where a number maps to a string. 9 is four letters, the rest are 3.
parents	intuition

editorial
content	Leetcode Editorial
children	lock_in_letters, recursion_reason_why_digits_size_small, recursive_solution, solutions_mine_vs_theirs, backtracking_function

recursive_solution
content	The suggestion in the editorial is to use recursion, which makes sense. A language like LISP could probably express this quite elegantly.
children	recursion_explanation
parents	editorial

lock_in_letters
content	The phrase "lock in letters" is used.
parents	editorial

backtracking_function
content	The recursive function is referred to as a "backtracking function".
parents	editorial

recursion_reason_why_digits_size_small
content	I noticed that the constraints for the input digits was very small (4 max). In the past, this has been a hint for a dynamic programming solution. But, this one could be related to recursion? (also, combinations can get quite large quite quickly).
parents	editorial

recursion_explanation
content	The idea here is you are using recursion to build up a string, which implicitely is like having a nested loop of arbitrary size. You start with an empty, string, add characters to it. The recursive call appends a letter to the end of the string, and moves the index position forward one. When a string is the length of the number of digits (base case), it gets appeneded to a list of combinations.
parents	recursive_solution

solutions_mine_vs_theirs
content	My solution ultimately was about pre-computing the number of combinations and in a loop computing the combinations with a means of keeping track of state. The leetcode solution involved expressing that problem in terms of recursion. My solution was more imperative, something you'd think about writing in a language like C where stack smashing is real. My solution would scale better than the recursive solution. But, it is less expressive. This problem is very well suited for a functional programming language.
parents	editorial