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

1. Define the Interface

Input: digits (numbers in a string)
Output array of strings (combinations)

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

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

1. Build on the partial result, pass on the partial, tell the child to take from second string, what position 2nd list, 1st position ‘ad’.
2. 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.
3. Use a wrapper method for backtracking. Pass the empty array. The combination size is the same as the size of the digits string.
4. Unit of Work. Choosing a letter from the given subset.
5. Should we do the UoW before or after the recursive call? It does not matter. You can do it any way you like.
6. Example 2 is a base case.
7. Example 3 is not a base case.

Example 3:

digits = 2
return the mapping for 2: ['a', 'b', 'c']

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

1. Pass 2 and 3, chop off the digits, we can check if digits is empty
2. Check the length of the partial and check for its size (same as digits size)
3. 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.

1. 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.
2. 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
3. What is an example that you can come up with that is different?

HOW

Wear the Programmer Hat (Implementation Details)

Analyze the Solution

1. Map the digit to character. - 2 to 9. Map the digits from 2 to 9 to abc, def, ghi
2. Recursion, Backtracking
3. Verify the output. Is there any relationship between the input and output.
4. 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.
5. What is the repeated unit of work that each recursive call must do?

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def mapping(digit)
  digits = {
    '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']
  }
  return digits[digit]
end

# @param {String} digits
# @return {String[]}    
def backtrack(combination, index, digits, output)
  if index == digits.size
    output << combination.join
    return
  end
    
  letters = mapping(digits[index])
  for i in (0..letters.size-1)
    # Choose
    combination << letters[i]
    # Explore
    backtrack(combination, index+1, digits, output)
    # unchoose
    combination.pop
  end
end

def letter_combinations(digits)
  output = []
  combination = []

  if digits.empty?
    return []
  end
  backtrack(combination, 0, digits, output)
  output
end

Final Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

def getWordsFromPhoneNumber(phoneNumber)
  output = []
  combination = []

  return [] if phoneNumber.empty?
  
  backtrack(combination, 0, phoneNumber, output)

  if output.empty?
    return ["-1"]
  else
    return output
  end
end

def mapping(digit)
  digits = {
    '0' => [],
    '1' => [],
    '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']
  }
  return digits[digit]
end

def backtrack(combination, index, digits, output)
  if index == digits.size
    output << combination.join unless combination.empty?
    
    return
  end
    
  letters = mapping(digits[index])
  
  if letters.empty?
    backtrack(combination, index+1, digits, output)
  end
  
  for i in (0..letters.size-1)
    # Choose
    combination << letters[i]
    # Explore
    backtrack(combination, index+1, digits, output)
    # unchoose
    combination.pop
  end
end

p getWordsFromPhoneNumber('1010101')

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        mapping = {
            '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']
        }

        def combine(current, remaining_digits):
            if not remaining_digits:
                combinations.append(current)
                return

            for letter in mapping[remaining_digits[0]]:
                combine(current + letter, remaining_digits[1:])

        combinations = []
        combine("", digits)
        return combinations

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.

1. Define the Interface Input: digits (numbers in a string) Output array of strings (combinations)

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

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.

4. Unit of Work Choosing a letter from the given subset

5. Should we do the UoW before or after the recursive call? It does not matter. You can do it any way you like.

6. Example 2 is a base case

7. Example 3 is not a base case.

Example 3:

digits = 2 return the mapping for 2: [‘a’, ‘b’, ‘c’]

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

1. Pass 2 and 3, chop off the digits, we can check if digits is empty
2. Check the length of the partical and check for its size (same as digits size)
3. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# @param {String} digits
# @return {String[]}

def mapping(digit)
    digits = {
    '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']
   }
    return digits[digit]
end

def backtrack(combination, index, digits, output)
    if index == digits.size
        output << combination.join
        return
    end

    letters = mapping(digits[index])
    for i in (0..letters.size-1)
#        Choose
        combination << letters[i]
#         Explore
        backtrack(combination, index+1, digits, output)
#         unchoose
        combination.pop
    end
end


def letter_combinations(digits)
    output = []
    combination = []
    if digits.empty?
        return []
    end
    backtrack(combination, 0, digits, output)
    output
end

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:

1. Combinations
2. Letter Combinations
3. 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        phone = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []

        def backtrack(combination, next_digits):
            if not next_digits:
                res.append(combination)
                return

            for letter in phone[next_digits[0]]:
                backtrack(combination + letter, next_digits[1:])

        backtrack("", digits)
        return res

Language Agnostic Coding Drills

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

2. Recursion: This problem solution involves the use of recursive function calls. Specifically, it uses the technique of backtracking, which is a type of recursion.

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

4. String Manipulation: This problem involves manipulating strings, by concatenating characters and slicing strings.

5. List Manipulation: In this problem, you need to know how to create a list, add elements to it, and return it.

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

1. Write a simple class with a method in your preferred language.
2. Write a function to manipulate strings (e.g., concatenation, slicing).
3. Write a function to manipulate lists (e.g., appending elements, returning lists).
4. Create and manipulate a dictionary.
5. Write a recursive function to solve a simple problem (e.g., factorial, Fibonacci sequence).
6. Write a function using backtracking to solve a problem such as generating all permutations of a string.

Solution for Coding Drills in Python

1. Write a simple class with a method in Python:

1
2
3

class SimpleClass:
    def hello(self):
        return "Hello, World!"

2. Write a function to manipulate strings (e.g., concatenation, slicing):

1
2
3
4
5
6
7
8

def manipulate_string():
    s = "Hello"
    s += ", World!" # Concatenation
    print(s)
    
    # Slicing
    first_five_chars = s[:5]
    print(first_five_chars)

3. Write a function to manipulate lists (e.g., appending elements, returning lists):

1
2
3
4
5
6

def manipulate_list():
    lst = [1, 2, 3]
    lst.append(4) # Appending an element
    print(lst)
    
    return lst

4. Create and manipulate a dictionary:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def manipulate_dict():
    # Creating a dictionary
    d = {'one': 1, 'two': 2, 'three': 3}
    
    # Accessing an element
    print(d['two'])
    
    # Iterating over a dictionary
    for key, value in d.items():
        print(f'Key: {key}, Value: {value}')

5. Write a recursive function to solve a simple problem (e.g., factorial, Fibonacci sequence):

1
2
3
4
5

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

6. Write a function using backtracking to solve a problem such as generating all permutations of a string:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  

string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)