Solutions

        

# O(n * 4^n) time, O(n * 4^n) space (each digit can map to 3 or 4 letters, so we have at most 4^n combinations, and each combination is of length n)
def letterCombinations(digits: str) -> list[str]:
    res =[]
    if not digits:
        return res

    keyboard = ["", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    curr = []

    def dfs(i: int, curr: list[str]):
        if len(curr) == len(digits):
            res.append("".join(curr))
            return

        for letter in keyboard[int(digits[i])-1]:
            curr.append(letter)
            dfs(i+1, curr)

            # backtrack
            curr.pop()

    dfs(0, curr)
    return res
    
# Iterative approach: start with an empty string, and for each digit, add the corresponding letters to all existing combinations to create new combinations.
# Similar to BFS, level-wise traversal.
# O(3^n) time, O(3^n) space (each digit can map to 3 or 4 letters, so we have at most 4^n combinations)
def letterCombinations1(digits: str):
    letters = ["", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    res = []
    if not digits:
        return res

    res = [""]
    for digit in digits:
        tmp = []
        for curStr in res:
            for c in letters[int(digit)-1]:
                tmp.append(curStr + c)
        res = tmp

    return res