LC 17

Solution to LeetCode 17 Letter Combinations of a Phone Number.

LeetCode 17

Letter Combinations of a Phone Number (Easy). [link]

1. Combinations via DFS. It’s easy to come up with ‘Recursion’ when it comes to ‘all combinations’. The function DFS has a structure of DFS(combination, nextDigit) and operates when nextDigit is not empty, do DFS(combination + letter, nextDigit[1:]).

   Time complexity O(3^m * 4^n), where m is the number of the numbers representing 3 letters, n is the number of the numbers representing 4 letters. Space complexity is O(3^m * 4^n + (m+n))

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits: return []
        Map = {'2':['a','b','c'],
                 '3':['d','e','f'],
                 '4':['g','h','i'],
                 '5':['j','k','l'],
                 '6':['m','n','o'],
                 '7':['p','q','r','s'],
                 '8':['t','u','v'],
                 '9':['w','x','y','z']}
        
        def recursion(combination, nextDigit):
            if len(nextDigit) == 0: # stop condition
                res.append(combination)
            else:
                for letter in Map[nextDigit[0]]:
                    recursion(combination + letter, nextDigit[1:])
        res = []
        backtrack('', digits)
        return res
                

2. Combinations via BFS. We use Queue data structure to implement a BFS.

   Time complexity O(3^m * 4^n). Space complexity O(2*(3^m * 4^n)).

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits: return []
        Map = {'2':['a','b','c'],
                 '3':['d','e','f'],
                 '4':['g','h','i'],
                 '5':['j','k','l'],
                 '6':['m','n','o'],
                 '7':['p','q','r','s'],
                 '8':['t','u','v'],
                 '9':['w','x','y','z']}
        res = ['']
        for i in digits:
            for _ in range(len(res)):
                tmp = res.pop(0)
                for j in Map[i]:
                    res.append(tmp+j)
        return res