17. Letter Combinations of a Phone Number

link

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

        if not digits:
            return []

        M = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }

        result = []
        
        n = len(digits)

        def backtrack(digits, s, n, current):
            if s == n:
                result.append(current)
                return
            
            for ss in M[digits[s]]:
                current += ss
                backtrack(digits, s+1, n, current)
                current = current[:-1]

        backtrack(digits, 0, n, "")

        return result