https://leetcode.com/problems/letter-combinations-of-a-phone-number

letter_combinations.py

DIGIT_TO_LETTERS = {
    "2": ["a", "b", "c"],
    "3": ["d", "e", "f"],
    "4": ["g", "h", "i"],
    "5": ["j", "k", "l"],
    "6": ["m", "n", "o"],
    "7": ["p", "q", "r", "s"],
    "8": ["t", "u", "v"],
    "9": ["w", "x", "y", "z"],
}

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []

        length = len(digits)
        # letter options at each position
        options = [DIGIT_TO_LETTERS[digit] for digit in digits]

        res = []
        def dfs(i: int, idxs: list[int]):
            # idxs is a list that tracks which letter we chose to use at each position
            
            # base case
            if i == length:
                res.append(
                    "".join(
                        options[digit_idx][idx]
                        for digit_idx, idx in enumerate(idxs)
                    )
                )
                return

            # vary idxs[i] and start new chains of DFS
            # by only incrementing indices in a systematic way, we avoid the need to "backtrack" by popping or resetting idxs
            for j in range(0, len(options[i])):
                idxs[i] = j
                dfs(i + 1, idxs)

            # this is unnecessary, doing this changes nothing as idxs is no longer needed at this point
            # idxs[i] = 0
            return

        dfs(0, [0 for _ in range(length)])
        return res
    
        # this doesn't work, not exhaustive enough, must do a DFS with backtracking approach
        # # start by varying the letters in the last position, and decrement i towards 0 (the first position) 
        # i = length - 1
        # # j will iterate through all options at current position, incrementing from 0
        # j = 0
        # while i >= 0:  # and j < len(options[i]):
        #     curr_letters = [options[digit_idx][idx] for digit_idx, idx in enumerate(idxs)]
        #     res.append("".join(curr_letters))

        #     # increment j and update idxs
        #     j += 1
        #     if j == j_maxs[i]:
        #         # reset j to 0, decrement i, set next j to 1
        #         idxs[i] = 0
        #         i -= 1
        #         j = 1
        #         idxs[i] = j
        #     else:
        #         idxs[i] = j