Letter Combinations
title: Letter Combinations of a Phone Number tags: combination backtracking choose-explore-unchoose
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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range [‘2’, ‘9’].
0 and 1 cannot be used
Thinking Process
- Define the Interface
Input: digits (numbers in a string)
Output array of strings (combinations)
- Define the Term
Combination - Order doesn’t matter, membership matters (1,2,3) is same as (2,1,3) Permutation - Order does matter (1,2,3) is different from (2,1,3)
- Classify the Problem Type
- 0-1 Knapsack Problem
- 0-1 or Fractional
- Bounded or Unbounded
- Since we don’t have a capacity that decides what goes into the Knapsack. This is NOT a knapsack problem.
7 9
pqrs wxyz
jkl. wxyz
def def
2 3
['a', 'b, 'c'] ['d', 'e, 'f']
0 1 2
First element from the first subset
ad
ae
af
Second element
bd
be
bf
Third element
cd
ce
cf
Total permutations = length of the possible letters for first x length of the possible letters
- Build on the partial result, pass on the partial, tell the child to take from second string, what position 2nd list, 1st position ‘ad’.
- How to store this letter combination in the output? Where to append the letter combination?
- Check for the length of the partial.
- If it is equal to the size of the digits, append it to the output array.
- Use a wrapper method for backtracking. Pass the empty array. The combination size is the same as the size of the digits string.
- Unit of Work. Choosing a letter from the given subset.
- Should we do the UoW before or after the recursive call? It does not matter. You can do it any way you like.
- Example 2 is a base case.
- Example 3 is not a base case.
Example 3:
digits = 2
return the mapping for 2: ['a', 'b', 'c']
- Backtracking Algorithm
How do we keep track of the partial combinations? It does not matter. You can do it any way you like. Declare a global variable and all your problems will be solved. Extract one digit from the digits and get its letter array [‘a’, ‘b’, ‘c’] Extract second digit from the digits and get its letter array [’d’, ’e’, ‘f’] We now have a,b,c and d,e,f, how do we create the combinations? We need a partial array to store the combination. We can push and pop the letters.
Take the mapping for first digit and:
- We push a letter on the partial array
- Explore the rest of the characters
Iterate over all the possible letters for the first digit:
- Include the letter (Choose)
- Explore rest of the options by recursion
- Exclude the letter (Unchoose)
In the base case, we will add the combination to the partial when the partial length is the same as the digits length.
Three ways to formulate the base case:
- Pass 2 and 3, chop off the digits, we can check if digits is empty
- Check the length of the partial and check for its size (same as digits size)
- String is a linearly ordered, use the index.
- Initialize the index as 0
- recurse(index+1)
- if index == length of digits we can save the partial in the output
Time and Space Complexity
Time: O( ) Space: O( )
Look for patterns.
Concretely —-> Abstract Concrete cases —-> Generalization
Base case Recursive cases
Understanding the Problem (Analyze the Problem). Wear the System Analyst Hat.
- Search for invariant
- We need to derive from the problem statement
- What does not vary in this problem?
- Length of every letter combination must be of the same size as the input
- Result can be in any order
1.1 If it is unknown, solve the problem by hand.
- Look for the clues in the problem space.
Classify the problem type
- Have I seen a problem like this before? Subsets - Good attempt, it is one way to solve the problem Variation of permutation problem
- What is an example that you can come up with that is different?
HOW
Wear the Programmer Hat (Implementation Details)
Analyze the Solution
- Map the digit to character. - 2 to 9. Map the digits from 2 to 9 to abc, def, ghi
- Recursion, Backtracking
- Verify the output. Is there any relationship between the input and output.
- How to generate the output?
- Start with an empty string. Why do we start with the smallest instance of the problem? - Base case Must provide a way to bail out. Avoid infinite recursion. To prevent invalid input from crashing your recursive logic Simplification allows reason about the problem easily First number, recursive case - We need to do the unit of work for a recursive call.
- What is the repeated unit of work that each recursive call must do?
Implementation
|
|
Final Solution
|
|
To solve this problem, we can use a recursive approach to generate all possible combinations of the letters that correspond to the given digits. We’ll create a function that iterates through the letters of the current digit and recursively calls itself for the remaining digits, combining the letters in all possible ways.
Here’s the code implementing this approach:
|
|
This code works by building combinations starting from the first digit and going on to the next ones, using the mapping of digits to letters as given in the problem statement. It returns all possible combinations that can be formed with the given digits, and it handles the edge cases of empty input correctly.
Define the Interface Input: digits (numbers in a string) Output array of strings (combinations)
Define the Term Combination - Order does not matter, membership matters (1,2,3) is same as (2,1,3) Permutation - Order does matter (1,2,3) is different from (2,1,3)
Classify the Problem Type 0-1 Knapsack Problem 0-1 or Fractional Bounded or Unbounded Since we don’t have a capacity that decides what goes into the Knapsack, this is NOT a knapsack problem.
[‘a’, ‘b’, ‘c’] [’d’, ’e’, ‘f’]
First element from the first subset ad ae af
Second element bd be bf
Third element cd ce cf
The combination size is the same as the size of the digits string.
Unit of Work Choosing a letter from the given subset
Should we do the UoW before or after the recursive call? It does not matter. You can do it any way you like.
Example 2 is a base case
Example 3 is not a base case.
Example 3:
digits = 2 return the mapping for 2: [‘a’, ‘b’, ‘c’]
- Backtracking Algorithm How do we keep track of the partial combinations? It does not matter. You can do it any way you like. Declare a global variable and all your problems will be solved.
Extract one digit from the digits and get its letter array [‘a’, ‘b’, ‘c’]
Extract second digit from the digits and get its letter array [’d’, ’e’, ‘f’]
We now have a,b,c and d,e,f, how do we create the combinations?
We need a partial array to store the combination We can push and pop the letters
Take the mapping for first digit and: We push a letter on the partial array Explore the rest of the characters Iterate over all the possible letters for the first digit
- Include the letter (Choose)
- Explore rest of the options by recursion
- Exclude the letter (Unchoose)
In the base case, we will add the combination to the partial when the partial length is the same as the digits length
Three ways to formulate the base case:
- Pass 2 and 3, chop off the digits, we can check if digits is empty
- Check the length of the partical and check for its size (same as digits size)
- String is a linearly ordered, use the index initialze the index as 0 recurse(index+1) if index == length of digits we can save the partial in the output
|
|
Identifying Problem Isomorphism
“Letter Combinations” is approximately isomorphic to “Generate Parentheses”.
Reasoning:
Both deal with the generation of all possible combinations from a given set of elements. In “Letter Combinations”, you’re asked to generate all possible letter combinations that the number could represent on a mobile phone keypad. In “Generate Parentheses”, you’re asked to generate all combinations of well-formed parentheses. Both problems require a depth-first search or backtracking approach to generate all combinations.
“Combinations” is another similar problem.
Reasoning: This problem asks for all possible combinations of k numbers out of 1 through n. It shares a structural similarity with “Letter Combinations” in that it involves creating all possible combinations from a set of elements.
Based on simplicity, the order is:
- Combinations
- Letter Combinations
- Generate Parentheses
“Combinations” is simpler as it only involves choosing k elements out of n. “Letter Combinations” is more complex because it requires mapping numbers to letters and then generating combinations. “Generate Parentheses” is the most complex, as it involves generating combinations while ensuring the parentheses are well-formed.
|
|
Language Agnostic Coding Drills
Basic Syntax: Understanding the syntax of the language you are using is the first step. This includes understanding how to define classes, methods, loops, conditionals, data structures like dictionaries and lists.
Recursion: This problem solution involves the use of recursive function calls. Specifically, it uses the technique of backtracking, which is a type of recursion.
Backtracking: Backtracking involves making an initial choice, then making further choices to solve the problem. If at any point the choices made are found to be incorrect, it “backs up” to a previous step and makes a different choice.
String Manipulation: This problem involves manipulating strings, by concatenating characters and slicing strings.
List Manipulation: In this problem, you need to know how to create a list, add elements to it, and return it.
Dictionary: This problem involves using a dictionary to map digits to corresponding letters. This requires understanding how to create a dictionary, access its elements, and iterate over it.
The drills, arranged in increasing order of difficulty, would be as follows:
- Write a simple class with a method in your preferred language.
- Write a function to manipulate strings (e.g., concatenation, slicing).
- Write a function to manipulate lists (e.g., appending elements, returning lists).
- Create and manipulate a dictionary.
- Write a recursive function to solve a simple problem (e.g., factorial, Fibonacci sequence).
- Write a function using backtracking to solve a problem such as generating all permutations of a string.
Solution for Coding Drills in Python
- Write a simple class with a method in Python:
|
|
- Write a function to manipulate strings (e.g., concatenation, slicing):
|
|
- Write a function to manipulate lists (e.g., appending elements, returning lists):
|
|
- Create and manipulate a dictionary:
|
|
- Write a recursive function to solve a simple problem (e.g., factorial, Fibonacci sequence):
|
|
- Write a function using backtracking to solve a problem such as generating all permutations of a string:
|
|