0017.Letter Combin of Phone Number

Link: 17. Letter Combinations of a Phone Number - Medium
Track: Amazon Tag

Question

Restate

• Given a string digits containing digits 2–9,
• return all possible letter combinations that the number could represent on a phone keypad. Return in any order.

Edge Case

• digits == "" → return []

---

Method 1 - (Optimal) backtracking
Method 2

Method

Approach

(discussed at lease two approach?)

Complexity

• Time Complexity: O($n\ast 4^n$)
• Space Complexity: O(n)

Code

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
            
        dic = {
            "2": "abc", "3":"def",
            "4": "ghi", "5":"jkl", "6":"mno",
            "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        res = []
        def dfs(idx, path):
            if len(path) == len(digits):
                res.append("".join(path))
                return
 
            for char in dic[digits[idx]]:
                path.append(char)
                dfs(idx + 1, path)
                path.pop()
        
        dfs(0, [])
        return res

---

History

• Jan-xx-2026 Peeked