0017-letter-combinations-of-a-phone-number

Try it on leetcode

Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

  • 1 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Solution(Python)

class Solution:
    def __init__(self):
        self.hashTable = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        self.hashList =  [
            "abc", 
            "def", 
            "ghi", 
            "jkl",
            "mno", 
            "pqrs", 
            "tuv", 
            "wxyz"
        ]
        

    def letterCombinations(self, digits: str) -> List[str]:
        return self.dfs(digits)
   
    # Time Complexity: O(4^n)
    # Space Complexity: O(4^n)
    def bfs(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
        res = []
        queue = deque([""])
        
        while queue:
            s = queue.popleft()
            
            if len(s) == n:
                res.append(s)
            else:
                for letter in self.hashList[int(digits[len(s)])]:
                    queue.append(s+letter)
        
        return res
   
    # Time Complexity: O(4^n*n)
    # Space Complexity: O(n)
    def dfs(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
        res = []
        
        def backtrack(candidate,i):
            if len(candidate) == n:
                res.append("".join(candidate))
                return
            letters = self.hashTable[digits[i]]
            for letter in letters:
                candidate.append(letter)
                backtrack(candidate,i+1)
                candidate.pop()
        backtrack([],0)
        return res
    
    
        

Dry Run