💡Letter Combinations of a Phone Number | Backtracking in Python | #LeetCode75 #Python #Backtracking

In this LeetCode 75 problem, we are given a string of digits from 2 to 9 and must generate all possible letter combinations that the number could represent based on a telephone keypad mapping.

Problem Details:

Each digit maps to a set of letters as follows:

2 → "abc"

3 → "def"

4 → "ghi"

5 → "jkl"

6 → "mno"

7 → "pqrs"

8 → "tuv"

9 → "wxyz"

The task is to return all possible letter combinations for the input digit string.

If the input string is empty, return an empty list.

Approach:

We use a backtracking technique which is ideal for exploring all possible combinations:

Mapping Initialization:

We create a dictionary called phone_map that maps each digit (as a string) to its corresponding letters.

This map will be used to look up the possible letters for each digit in the input.

Backtracking Function:

Define a helper function backtrack(index, current_combination) that:

Base Case: When index equals the length of the input string, we add the built combination to our results list because we have processed all digits.

Recursive Case: For the current digit at digits[index], loop through all letters from phone_map and recursively build combinations by appending each letter.

This process ensures that all possible combinations are explored, one digit at a time.

Initiate Backtracking:

We start with an empty combination and begin at index 0.

As the recursion unwinds, every valid combination is added to the result list.

Return Results:

After completing the backtracking, the result list will contain every possible letter combination that the digits can represent.

Advantages of Backtracking:

Efficient for Small Inputs: Since the maximum length of digits is 4, even exponential complexity is acceptable.

Systematic Exploration: Backtracking allows us to explore all possible combinations in a clean and systematic manner.

Recursion & Simplicity: The recursive approach is elegant and easier to understand and implement for generating combinations.

Python Code Implementation:

class Solution:
def letterCombinations(self, digits):
if not digits:
return []

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

result = []

def backtrack(index, current_combination):
# Base Case: All digits are processed, add combination to result
if index == len(digits):
return
# Recursive Case: Process the current digit and all its possible letters
current_digit = digits[index]
for letter in phone_map[current_digit]:
backtrack(index + 1, current_combination + letter)

# Initiate backtracking with an empty string at index 0
backtrack(0, "")
return result

# Example Usage:

sol = Solution()

Complexity Analysis:

Time Complexity: O(3^n * 4^n) in the worst-case scenario, but since n ≤ 4, the total number of combinations is at most 4^4 = 256.

Space Complexity: O(n) due to recursion stack, where n is the length of digits.

#LeetCode75, #Backtracking, #Python, #Coding, #Algorithm, #Recursion, #DSA, #TelephoneKeypad, #CodingInterview