backtracking_1.py

# Given a combination of digits e.g. 23
# Generate all possible combinations of alphabets it can create on an old telephone
# e.g. 23 ==> ["ad","ae","af","bd","be","bf","cd","ce","cf"]

# Done Using Backtracking Approach in Python


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

        def get_neighbours(index):
            try:
                letter = digits[index + 1]
            except IndexError:
                return ""
            return mappings[letter]


        def dfs(current_index, current_selection):
            to_return = []

            neighbours = get_neighbours(current_index)
            if current_selection and not neighbours:
                to_return.append(current_selection)
            else:
                for neighbour_letter_selection in neighbours:
                    # Get all downstream selections
                    st = dfs(current_index=current_index + 1, current_selection=neighbour_letter_selection)
                    
                    # add current_selection to all downstream selections
                    for s in st:
                        to_return.append(current_selection + s)

            return to_return
        
        return dfs(-1, "")