Letter Combinations of a Phone Number -Python

 Problem Statement

       In this problem, we are given a string of digits from 2 to 9.

Each digit represents some letters (just like on a mobile phone keypad).

Our task is to find all possible letter combinations that can be formed using those digits.

Phone Keypad Mapping

Each number maps to certain letters:

• 2 → abc
• 3 → def
• 4 → ghi
• 5 → jkl
• 6 → mno
• 7 → pqrs
• 8 → tuv
• 9 → wxyz

For example:

• Input "2" → Output ["a", "b", "c"]
• Input "23" → Combine letters of 2 and 3    

Understanding the Idea (Simple Way)

Let’s take input "23":

• Digit 2 gives → a, b, c
• Digit 3 gives → d, e, f

Now we combine them:

• a → ad, ae, af
• b → bd, be, bf
• c → cd, ce, cf

So final output:

["ad","ae","af","bd","be","bf","cd","ce","cf"]

 We are basically trying all possible combinations.

Approach Used: Backtracking (Recursion)

We solve this using recursion, which means:

• Build the result step by step
• Try all possibilities
• Go deeper until a full combination is formed

Python Code with Explanation

def letterCombinations(digits):

Define a function that takes a string digits

 if not digits:
        return []

i}If input is empty, return empty list
ii} Because no digits means no combinations

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

• Create a dictionary to store digit → letters mapping
• This helps us quickly find letters for each number

result = []
This list will store all final combinations

2. def backtrack(index, path):

•  Create a helper function
• index → current position in digits
• path → current formed string (like "a", "ad")

3.if index == len(digits):
            result.append(path)
            return

->Base condition:

• If we reached the end of digits
• Add the current word to result
• Stop that recursion branch

•  letters = phone[digits[index]]

  i] Get letters for current digit
  ii]Example: digits[index] = "2" → letters = "abc"

4. for char in letters:

      ->Loop through each letter of that digit

  backtrack(index + 1, path + char)

•  Move to next digit
• Add current letter to path

 Example:

• "" → "a"
• "a" → "ad"

 backtrack(0, "")

 Start recursion from:

• index = 0 (first digit)
• empty string ""

  return result

 Return all combinations

Step-by-Step Flow (Visual)

For "23":

Start with ""
 ↓
Add 'a' → "a"
 ↓
Add 'd' → "ad" (correct)

Add 'e' → "ae" (correct)

Add 'f' → "af" (correct)


Add 'b' → "b"
 ↓
bd, be, bf (correct)


Add 'c' → "c"
 ↓
cd, ce, cf (correct)
  

Python Code
def letterCombinations(digits):
    if not digits:
        return []
    
    phone = {
        "2": "abc", "3": "def", "4": "ghi",
        "5": "jkl", "6": "mno", "7": "pqrs",
        "8": "tuv", "9": "wxyz"
    }
    
    result = []
    
    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        
        for char in phone[digits[index]]:
            backtrack(index + 1, path + char)
    
    backtrack(0, "")
    return result
Time Complexity
Each digit can have up to 4 letters
So total combinations = O(4^n)
(where n = number of digits)
Example Run
print(letterCombinations("23"))
Output:
['ad','ae','af','bd','be','bf','cd','ce','cf']

FINAL
This problem is very useful to understand:
Recursion
Backtracking
How to generate combinations
It is commonly asked in coding interviews and helps improve logical thinking.

---