[LeetCode] 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

 

Backtracking

Backtracking is an algorithmic techniqe used for solving problems by exploring all possible options systematically while eliminating paths that don't satisfy the problem's constraiints. It is particularly useful for problems involving combinations, permutations, and constraint satisfaction.

 

Key Concepts

- Systematic Exploration: It tries all possible solutions recursively.

- Pruning (Early Stoppigng) : Paths that cannot lead to a valid solution are abandoned early.

- State Restoration: After exploring a path, the state is reverted to allow exploration of other options.

 

How Backtracking Works

- Decision Making : Make a choice for the current step.

- Validation : Check if the current choice is valid under the given constraints.

- Recursive Exlopration: Move to the next step recursively.

- Backtrack ; If a path fails, undo the choice and try the next option.

 

 

My early code

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {
            '2': "abc",
            '3': "def",
            '4': "ghi",
            '5': "jkl",
            '6': "mno",
            '7': "pqrs",
            '8': "tuv",
            '9': "wxyz"
        }

        results = []

        def backtrack(combination, i):
            if i == len(digits):
                results.append(combination)
                return
            
            for s in phone[digits[i]]:
                backtrack(combination + s, i+1)

        backtrack("", 0)
        print(results)
        return [] if len(results)==1 else results

 

 

Feedback

 

def backtrack(combination, i):
    if i == len(digits):
        results.append("".join(combination))  # Convert to string before appending
        return
    
    for s in phone[digits[i]]:
        combination.append(s)  # Add character
        backtrack(combination, i + 1)
        combination.pop()  # Remove character after recursion

 

 

String concatenation (combination + s) can lead to inefficiencies in Python because strings are immutable. WHile it works fine for small inputs, for large inputs. it could impact performance.

 

Suggested Improvement:

Instead of creating new string, consider passing the combination as a list and appending characters. After recursion, backtrack by removing the last character. This is mor memory-eficient.

InPython, strings are immutable, meaning that every time you modify a stiring a new string object is created in memory. This happens because Python cannot modify the existing string in place.

 

When concatenating strings repeatedly in a recursive function, this can lead to increased memory usage(Every concatenation creates a new string object) and performance overhead(The program spends extra time creating and destorying intermediate strings). To avoid this, you can use a list to store the current combination. Lists in Python are mutable, meaning you can modify them in place without creating a new object each time.