Python easy to understand backtracking solution.


  • 10
    C
    def letterCombinations(self, digits):
        if not digits:
            return []
        dic = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        res = []
        self.dfs(digits, dic, 0, "", res)
        return res
        
    def dfs(self, digits, dic, index, path, res):
        if len(path) == len(digits):
            res.append(path)
            return 
        for i in xrange(index, len(digits)):
            for j in dic[digits[i]]:
                self.dfs(digits, dic, i+1, path+j, res)

  • 0

    I have similar idea but different implementation with make each dfs do more work.

    from collections import defaultdict
    
    class Solution(object):
        def letterCombinations(self, digits):
            if not digits: return []
            q = [self.table[c] for c in digits]
            return self.dfs(q)
        
        def dfs(self, queue, re=''):
            if not queue:
                return [re]
            return [x for c in queue[0] for x in self.dfs(queue[1:], re+c)]
        
        def __init__(self):
            self.table, start = defaultdict(list), 96
            for i in range(2, 10):
                count = 4 if i in [7, 9] else 3
                for _ in range(count):
                    start += 1
                    self.table[str(i)].append(chr(start))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.