5/09/2020

[LeetCode] 17. Letter Combinations of a Phone Number

Problem : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

This is a typical backtracking problem. Consider the code travels a tree. Each digit is represented as a node of this tree. Each node has the rest digits as its child node. On each node, the code has number N of letter to pick up. So the code does DFS on this tree to find all of the combination.

To simplify the calculation, consider each digits has 3 letters.

Time Complexity :  O ( 3 ** len(s) )
Space Complexity:  O ( 3 ** len(s) )

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        result = []
        
        def backtrack(i, tmp):
            if i == len(digits):
                if tmp:
                    result.append(tmp)
                return
                
            for t in letters[digits[i]]:
                backtrack(i+1, tmp + t)
        
        backtrack(0, "")
        
        return result

BFS based solution:


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        if not digits: return []
                
        result = []
        
        queue = deque([[l, 1] for l in letters[digits[0]]])
     
        while queue:
            for _ in range(len(queue)):
                w , index = queue.popleft()
                
                if index == len(digits):
                    result.append(w)
                else:
                    for l in letters[digits[index]]:
                        queue.append([w + l, index + 1])
        
        return result

An iterative solution. Start from the last digit to the first digit, add letter of current digit to the front of last letter combinations.


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        
        letters = {'2': 'abc', '3': 'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz' }
              
        ds = [d for d in digits]
        
        result = [[l] for l in letters[ds.pop()]]
        
        while ds:
            suffix = result[:]
            result = []
            
            for l in letters[ds.pop()]:
                for s in suffix:
                    result.append([l] + s)
            
        return [''.join(t) for t in result]

Edited 04/24/2021. Add the iterative solution.

No comments:

Post a Comment