Letter Combinations of a Phone Number -Leetcode

Imagine you have a classic “phone number to words” problem. Given a string of digits, each digit can be mapped to a set of letters (like on a telephone keypad). You are tasked with generating all possible valid words from a dictionary that can be constructed using the digits in sequence. This problem can be tackled efficiently using backtracking, a common technique for solving constraint satisfaction problems.

In this blog post, we will break down the backtracking solution to this problem and diagram to visualize the state tree, which represents the exploration of all possible combinations.

Understanding the Backtracking Approach

Backtracking is a systematic way to iterate through all possible configurations of a search space. For the phone dictionary problem, the search space is all possible combinations of letters that can be formed using the digits in the input string.

The key idea is to explore each possibility step-by-step, and if a partial solution cannot be completed to a valid solution, we backtrack and try another possibility. This technique ensures that we explore all potential combinations efficiently.

Problem Setup

1. Input:

   • A string of digits (e.g., “23”).
   • A dictionary of valid words (e.g., ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]).

2. Output:

   • All valid words from the dictionary that can be formed using the sequence of digits.

3. Mapping:

   • Each digit from 2 to 9 maps to a set of letters, similar to a traditional phone keypad:
     • 2 -> “abc”
     • 3 -> “def”
     • 4 -> “ghi”
     • 5 -> “jkl”
     • 6 -> “mno”
     • 7 -> “pqrs”
     • 8 -> “tuv”
     • 9 -> “wxyz”

Backtracking Algorithm

The backtracking solution can be implemented in a recursive manner:

1. Start with an empty current word and the first digit.
2. For each letter mapped to the current digit:
   • Append the letter to the current word.
   • Move to the next digit.
   • If the current word length is equal to the input digit string length, check if it is in the dictionary and add it to the result.
   • Backtrack by removing the last letter and exploring the next letter.

Code Implementation

Here’s a Python example of the backtracking solution:

def phone_dictionary(digits, dictionary):
    if not digits:
        return []

    # Mapping of digits to letters
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    # List to store the valid words
    result = []

    # Helper function for backtracking
    def backtrack(index, current_word):
        # Base case: If the current word length equals digits length
        if index == len(digits):
            if current_word in dictionary:
                result.append(current_word)
            return
        
        # Recursive case: Try each letter mapped to the current digit
        for letter in phone_map[digits[index]]:
            backtrack(index + 1, current_word + letter)

    # Start backtracking from the first digit
    backtrack(0, "")
    return result
# Example usage
digits = "23"
dictionary = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
print(phone_dictionary(digits, dictionary))  # Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']` 

JavaScript

function phoneDictionary(digits, dictionary) {
  if (digits.length === 0) return [];

  // Mapping of digits to letters
  const phoneMap = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
  };

  const result = [];

  // Helper function for backtracking
  function backtrack(index, currentWord) {
    // Base case: If the current word length equals digits length
    if (index === digits.length) {
      if (dictionary.includes(currentWord)) {
        result.push(currentWord);
      }
      return;
    }

    // Recursive case: Try each letter mapped to the current digit
    const letters = phoneMap[digits[index]];
    for (const letter of letters) {
      backtrack(index + 1, currentWord + letter);
    }
  }

  // Start backtracking from the first digit
  backtrack(0, '');
  return result;
}

// Example usage
const digits = '23';
const dictionary = ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'];
console.log(phoneDictionary(digits, dictionary)); // Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Visualizing the Backtracking State Tree

To better understand how backtracking explores different combinations, we can visualize the state tree using Mermaid.js. This visualization shows the decision points and backtracking steps.

Below is a diagram that represents the state tree for the input digits = "23":

Explanation of the Diagram

1. Start Node: The process begins with the first digit “2.”
2. Digit Node (D2): From digit “2,” we branch out to its corresponding letters: “a,” “b,” and “c.”
3. Next Digit (D3): For each letter of the first digit, we move to the next digit “3.”
4. Word Nodes (AD, AE, …): For each combination of letters formed, we check if the word is in the dictionary and, if valid, add it to the result.

The tree shows how each possible letter is explored, and if a valid word is found, the algorithm continues until all possibilities are exhausted. The branches represent all possible combinations generated by the digits.

Conclusion

Backtracking is a powerful technique for solving problems like the phone dictionary problem. By breaking down the problem into smaller subproblems and using a systematic exploration approach, we can efficiently generate all valid combinations. Visualizing the state tree provides a clearer understanding of how the backtracking algorithm works under the hood.