17. Letter Combinations of a Phone Number

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

        n = len(digits)
        hm = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        
        def backtrack(i: int, path: str) -> None:
            if i == n:
                result.append(path)
                return
            for letter in hm[digits[i]]:
                backtrack(i + 1, path + letter)

        result = []
        backtrack(0, '')
        return result